{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prime Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: primePalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文素数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>求出大于或等于&nbsp;<code>N</code>&nbsp;的最小回文素数。</p>\n",
    "\n",
    "<p>回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是<em>素数</em>。</p>\n",
    "\n",
    "<p>例如，2，3，5，7，11 以及&nbsp;13 是素数。</p>\n",
    "\n",
    "<p>回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是<em>回文数。</em></p>\n",
    "\n",
    "<p>例如，12321 是回文数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>6\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>8\n",
    "<strong>输出：</strong>11\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>13\n",
    "<strong>输出：</strong>101</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= N &lt;= 10^8</code></li>\n",
    "\t<li>答案肯定存在，且小于&nbsp;<code>2 * 10^8</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prime-palindrome](https://leetcode.cn/problems/prime-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prime-palindrome](https://leetcode.cn/problems/prime-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6', '8', '13']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        while True:\n",
    "            if self.isHeiwen(n) and self.isPrime(n):\n",
    "                return n\n",
    "            n+=1\n",
    "            if 10**7 < n < 10**8:\n",
    "                n = 10**8\n",
    "\n",
    "        \n",
    "    # def genHuiwen():\n",
    "    #     for k in range(1,9):\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def isHeiwen(self,n):\n",
    "        a = 0\n",
    "        b = n\n",
    "        while b>0:\n",
    "            a = a*10+b%10\n",
    "            b = b//10\n",
    "        if a==n:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    \n",
    "    def isPrime(self, n):\n",
    "        if n<2:\n",
    "            return False\n",
    "        i = 2\n",
    "        while i*i<=n:\n",
    "            if n%i==0:\n",
    "                return False\n",
    "            i+=1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "\n",
    "        # 判断是否是素数\n",
    "        def is_prime(n):\n",
    "            return n > 1 and all(n % x for x in range(2, int(n ** 0.5) + 1))\n",
    "\n",
    "        # 获取大于等于n的回文数\n",
    "        s = str(n)\n",
    "        while True:\n",
    "            # 翻转n的前半段（偶数位就直接是前半段折半，奇数位对称中点折半），组合成回文数\n",
    "            # 例如：5432 -> 5445；54321 -> 54345\n",
    "            # 这样翻转，一定是从N开始最小的回文数字开始遍历的\n",
    "            mid = len(s) // 2\n",
    "            first_half = s[:mid] # 前半段，如果是奇数位数，不包含中点\n",
    "            second_half = first_half[::-1] # 前半段翻转\n",
    "            first_half_with_mid = s[:len(s)-mid] # 偶数位就是前半段，奇数位数则是前半段加上中点数\n",
    "\n",
    "            final = int(first_half_with_mid + second_half)\n",
    "            \n",
    "            # 翻转前半部分，和后半部组合成的新数字，如果满足大于n的条件，就退出\n",
    "            if final >= n and is_prime(final):\n",
    "                return final\n",
    "            \n",
    "            # 如果得到的数小于N，则把N的前半段加一，再翻转\n",
    "            new_first_half_with_mid = str(int(first_half_with_mid) + 1)\n",
    "            s = new_first_half_with_mid + second_half\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        if n == 1: return 2\n",
    "        \n",
    "        target = n\n",
    "        while True:\n",
    "            if self.isSu(target) and self.isHui(target):\n",
    "                return target\n",
    "            target += 1\n",
    "            if 10_000_000 < target and target < 100_000_000:\n",
    "                target = 100_000_000\n",
    "\n",
    "    def isSu(self, target):\n",
    "        for i in range(2, int(sqrt(target)) + 1):\n",
    "            if target % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    def isHui(self, target):\n",
    "        rev_target = str(target)[::-1]\n",
    "        return rev_target == str(target\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def primePalindrome(self, N):\n",
    "        def is_prime(n):\n",
    "            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))\n",
    "\n",
    "        for length in range(1, 6):\n",
    "            #Check for odd-length palindromes\n",
    "            for root in range(10**(length - 1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-2::-1]) #eg. s = '123' to x = int('12321')\n",
    "                if x >= N and is_prime(x):\n",
    "                    return x\n",
    "                    #If we didn't check for even-length palindromes:\n",
    "                    #return min(x, 11) if N <= 11 else x\n",
    "\n",
    "            #Check for even-length palindromes\n",
    "            for root in range(10**(length - 1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-1::-1]) #eg. s = '123' to x = int('123321')\n",
    "                if x >= N and is_prime(x):\n",
    "                    return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        while n < 2 * 10 ** 8:\n",
    "            if self.isPalindrome(n) and self.isPrime(n):\n",
    "                return n\n",
    "            n += 1\n",
    "            if 10**7 < n < 10**8:\n",
    "                n = 10**8\n",
    "\n",
    "\n",
    "    def isPalindrome(self, n: int):\n",
    "        n_str = str(n)\n",
    "        return n_str == n_str[::-1]\n",
    "\n",
    "    def isPrime(self, n: int):\n",
    "        for i in range(2, int(math.sqrt(n) + 1)):\n",
    "            if n % i == 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, N: int) -> int:\n",
    "        if N <= 2:\n",
    "            return 2\n",
    "        while True:\n",
    "            s = str(N)\n",
    "            l = len(s)\n",
    "\n",
    "            # 思路1的实现\n",
    "            if l % 2 == 0 and l > 2:\n",
    "                N = 10 ** l\n",
    "                continue\n",
    "\n",
    "            # 思路2实现\n",
    "            if N > 10 and s[0] in ['2', '4', '5', '6', '8']:\n",
    "                N = (int(s[0]) + 1) * (10 ** (l - 1))\n",
    "                continue\n",
    "\n",
    "            # 思路3的实现\n",
    "            if s != s[::-1]:\n",
    "                N += 1\n",
    "                continue\n",
    "            # 判断素数\n",
    "            for n in range(2, int(N ** 0.5) + 1):\n",
    "                if N % n == 0:\n",
    "                    N += 1\n",
    "                    break\n",
    "            else:\n",
    "                return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isPalindrome(x):\n",
    "            return str(x) == str(x)[::-1]\n",
    "        \n",
    "        def isPrime(n): # include n\n",
    "            for i in range(2, int(sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return n >= 2\n",
    "        \n",
    "        while True:\n",
    "            if isPalindrome(n) and isPrime(n):\n",
    "                return n\n",
    "            n += 1\n",
    "            if len(str(n)) in [4, 6, 8]:\n",
    "                n = 10 ** len(str(n)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def is_prime(x):\n",
    "            for i in range(2,int(sqrt(x)) + 1):\n",
    "                if x % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        i = max(2,n)\n",
    "        while True:\n",
    "            if is_prime(i) and str(i) == str(i)[::-1]:\n",
    "                return i\n",
    "            i += 1\n",
    "            if 10**7 < i < 10**8:\n",
    "                i = 10**8\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        target = n\n",
    "        while True:\n",
    "            if self.isSu(target) and self.isHui(target):\n",
    "                return target\n",
    "            target += 1\n",
    "            if 10_000_000 < target and target < 100_000_000:\n",
    "                target = 100_000_000\n",
    "\n",
    "    def isSu(self, target):\n",
    "        for i in range(2, int(sqrt(target)) + 1):\n",
    "            if target % i == 0: return False\n",
    "        return target > 1 and True\n",
    "\n",
    "    def isHui(self, target):\n",
    "        rev_target = str(target)[::-1]\n",
    "        return rev_target == str(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 2\n",
    "\n",
    "        def is_prime(n):\n",
    "            for i in range(2, math.floor(math.sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while True:\n",
    "            if n % 2 == 0:\n",
    "                n+= 1\n",
    "                continue\n",
    "            s = str(n)\n",
    "            if len(s) == 8:\n",
    "                n = 10 ** 8\n",
    "                continue\n",
    "            if s == s[::-1] and is_prime(n):\n",
    "                return n\n",
    "            n += 2\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def reverse(n):\n",
    "            ans=0\n",
    "            while n :\n",
    "                ans=ans*10+n%10\n",
    "                n=n//10\n",
    "            return ans\n",
    "        def isPrime(x):\n",
    "            if x==1: return False\n",
    "            for i in range(2,int(x**.5+1)):\n",
    "                if x%i ==0: \n",
    "                    return False\n",
    "            return True\n",
    "        while 1:\n",
    "            if n==reverse(n) and isPrime(n):\n",
    "                return n\n",
    "            n+=1\n",
    "            if 10**7 < n < 10**8:\n",
    "                n=10**8\n",
    "                   \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def primePalindrome(self, N):\n",
    "        def is_prime(n):\n",
    "            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))\n",
    "\n",
    "        for length in range(1, 6):\n",
    "            #Check for odd-length palindromes\n",
    "            for root in range(10**(length - 1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-2::-1]) #eg. s = '123' to x = int('12321')\n",
    "                if x >= N and is_prime(x):\n",
    "                    return x\n",
    "                    #If we didn't check for even-length palindromes:\n",
    "                    #return min(x, 11) if N <= 11 else x\n",
    "\n",
    "            #Check for even-length palindromes\n",
    "            for root in range(10**(length - 1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-1::-1]) #eg. s = '123' to x = int('123321')\n",
    "                if x >= N and is_prime(x):\n",
    "                    return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def isPrime(n):  \n",
    "\n",
    "            if n <= 1:  \n",
    "\n",
    "                return False \n",
    "\n",
    "            i = 2 \n",
    "\n",
    "            while i*i <= n:  \n",
    "\n",
    "                if n % i == 0:  \n",
    "\n",
    "                    return False \n",
    "\n",
    "                i += 1 \n",
    "\n",
    "            return True \n",
    "            \n",
    "        if n<12:\n",
    "            return min([x if x>=n else 11 for x in[2,3,5,7,11]])\n",
    "        \n",
    "        l=len(str(n))\n",
    "        if 1%2==0:\n",
    "            n=(10**l)+1\n",
    "        \n",
    "        t0=10**(l//2)\n",
    "        if t0>0:\n",
    "            p=n//t0\n",
    "            while 1:\n",
    "                ns0=str(p)\n",
    "                ns1=ns0[::-1][1:]\n",
    "                \n",
    "                ns=int(ns0+ns1)\n",
    "                if not isPrime(ns) or ns<n:\n",
    "                    p=p+1\n",
    "                else:\n",
    "                    return ns\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "\n",
    "        # 判断是否是素数\n",
    "        def is_prime(n):\n",
    "            return n > 1 and all(n % x for x in range(2, int(n ** 0.5) + 1))\n",
    "\n",
    "        # 获取大于等于n的回文数\n",
    "        def find_p_larger_than_n(n):\n",
    "            while True:\n",
    "                # 翻转n的前半段，组合成回文数（偶数位就直接是前半段折半，奇数位对称中点折半）\n",
    "                # 例如：5432 -> 5445；54321 -> 54345\n",
    "                # 如果得到的数小于N，则把N的前半段加一，再翻转\n",
    "                # 这样翻转，一定是从N开始最小的回文数字开始遍历的\n",
    "                s = str(n)\n",
    "                mid = len(s) // 2\n",
    "                first_half = s[:mid]\n",
    "                second_half = first_half[::-1] # 前半段翻转\n",
    "                # 最终回文字符串=原字符串前半段（可能还包含一个中点数）+翻转前半段得到的后半段\n",
    "                first_half_with_mid = s[:len(s)-len(second_half)]\n",
    "                final = first_half_with_mid + second_half\n",
    "                if int(final) >= n:\n",
    "                    return int(final)\n",
    "                \n",
    "                # 如果比n小，需要前半段+1，再翻转\n",
    "                first_half_with_mid_str = str(int(first_half_with_mid) + 1)\n",
    "                n = int(first_half_with_mid_str + second_half)\n",
    "                \n",
    "        while True:\n",
    "            n = find_p_larger_than_n(n)\n",
    "            if is_prime(n):\n",
    "                return n\n",
    "            n += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 2\n",
    "        while True:\n",
    "            s = str(n)\n",
    "            l = len(s)\n",
    "            if n > 10 and s[0] in ['2','4','6','8']:\n",
    "                n = (int(s[0])+1)*10**(l-1)\n",
    "                continue\n",
    "            if l%2 == 0 and l > 2:\n",
    "                n = 10**(l)\n",
    "                continue\n",
    "            if s != s[::-1]:\n",
    "                n += 1\n",
    "                continue\n",
    "            for i in range(2,int(n**0.5)+1):\n",
    "                if n % i == 0:\n",
    "                    n += 1\n",
    "                    break\n",
    "            else:\n",
    "                return n\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "                \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isp(x):\n",
    "            return x > 1 and all(x %d for d in range(2, int(math.sqrt(x))+1))\n",
    "        \n",
    "        def reverse(x):\n",
    "            a = 0\n",
    "            while x >0:\n",
    "                a = a * 10 + x % 10\n",
    "                x //= 10 \n",
    "            return a \n",
    "        if n <= 2:\n",
    "            return 2\n",
    "        if n % 2==0:\n",
    "            n += 1\n",
    "        while True:\n",
    "            if n == reverse(n) and isp(n):\n",
    "                return n \n",
    "            n+=2\n",
    "            if 10**7 < n < 10**8:\n",
    "                n = 10**8+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, N: int) -> int:\n",
    "        if N <= 2:\n",
    "            return 2\n",
    "        while True:\n",
    "            s = str(N)\n",
    "            l = len(s)\n",
    "\n",
    "            # 思路1:大于两位数的偶数位数都不存在回文素数\n",
    "            if l % 2 == 0 and l > 2:\n",
    "                N = 10 ** l\n",
    "                continue\n",
    "\n",
    "            # 思路2:以24568开头的多位数肯定不会是回文素数\n",
    "            if N > 10 and s[0] in ['2', '4', '5', '6', '8']:\n",
    "                N = (int(s[0]) + 1) * (10 ** (l - 1))\n",
    "                continue\n",
    "\n",
    "            # 判断回文\n",
    "            if s != s[::-1]:\n",
    "                N += 1\n",
    "                continue\n",
    "            # 判断素数\n",
    "            for n in range(2, int(N ** 0.5) + 1):\n",
    "                if N % n == 0:\n",
    "                    N += 1\n",
    "                    break\n",
    "            else:\n",
    "                return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isPrime(n):\n",
    "            return n>1 and all( n%x!=0 for x in range(2, int(n**0.5)+1 ) )\n",
    "        \n",
    "\n",
    "        for l in range(1, 6):\n",
    "            for root in range(10**(l-1), 10**l):\n",
    "                s = str(root)\n",
    "                x = s + s[-2::-1]\n",
    "                x = int(x)\n",
    "                if x>=n and isPrime(x):\n",
    "                    return x\n",
    "            \n",
    "            for root in range(10**(l-1), 10**l):\n",
    "                s = str(root)\n",
    "                x = s + s[-1::-1]\n",
    "                x = int(x)\n",
    "                if x>=n and isPrime(x):\n",
    "                    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def judge_prime(num):\n",
    "            if num==2:\n",
    "                return True\n",
    "            elif num%2==0:\n",
    "                return False\n",
    "            \n",
    "            for i in range(3, int(sqrt(num))+1):\n",
    "                if num%i==0:\n",
    "                    return False\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        if n==1 or n==0:\n",
    "            return 2\n",
    "\n",
    "\n",
    "        def find_root(num):\n",
    "            a = str(num)\n",
    "            k = len(a)\n",
    "            if k==1:\n",
    "                return 1\n",
    "\n",
    "            if k%2:\n",
    "                root = a[:(k+1)//2]\n",
    "                b = root[:-1]\n",
    "                b = b[::-1]\n",
    "                new_num = root + b\n",
    "                new_num = int(new_num)\n",
    "                if new_num>=num:\n",
    "                    root = int(root)\n",
    "                else:\n",
    "                    root = int(root)+1\n",
    "            else:\n",
    "                root = a[:k//2]\n",
    "                new_num = root + root[::-1]\n",
    "                new_num = int(new_num)\n",
    "                if new_num>=num:\n",
    "                    root = int(root)\n",
    "                else:\n",
    "                    root = int(root)+1\n",
    "            return root  \n",
    "\n",
    "        root = find_root(n)\n",
    "        max_num = -1\n",
    "\n",
    "        while True:\n",
    "            #奇数\n",
    "            a = str(root)\n",
    "            b = a[:-1]\n",
    "            b = b[::-1]\n",
    "            new_num = a + b\n",
    "            new_num = int(new_num)\n",
    "            if new_num>=n and judge_prime(new_num):\n",
    "                if max_num==-1:\n",
    "                    max_num = new_num\n",
    "                else:\n",
    "                    if max_num<=new_num:\n",
    "                        break\n",
    "                    else:\n",
    "                        max_num = new_num\n",
    "\n",
    "            #偶数\n",
    "            a = str(root)\n",
    "            new_num = a + a[::-1]\n",
    "            new_num = int(new_num)\n",
    "            if new_num>=n and judge_prime(new_num):\n",
    "                if max_num==-1:\n",
    "                    max_num = new_num\n",
    "                else:\n",
    "                    if max_num<=new_num:\n",
    "                        break\n",
    "                    else:\n",
    "                        max_num = new_num\n",
    "            \n",
    "            \n",
    "            root += 1\n",
    "        \n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isp(x):\n",
    "            return x > 1 and all(x %d for d in range(2, int(math.sqrt(x))+1))\n",
    "        \n",
    "        for length in range(1, 6):\n",
    "            for x in range(10**(length-1), 10**(length)):\n",
    "                s = str(x)\n",
    "                v = s + s[::-1][1:]\n",
    "                a = 0\n",
    "                for c in v:\n",
    "                    a = a * 10 + ord(c) - ord('0')\n",
    "                if a >= n and isp(a):\n",
    "                    return a \n",
    "            for x in range(10**(length-1), 10**(length)):\n",
    "                s = str(x)\n",
    "                v = s + s[::-1]\n",
    "                a = 0\n",
    "                for c in v :\n",
    "                    a = a * 10 + ord(c) - ord('0')\n",
    "                if a >= n and isp(a):\n",
    "                    return a \n",
    "            \n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        if n == 1: return 2\n",
    "        def test(val):\n",
    "            tmp = 2\n",
    "            while tmp * tmp <= val:\n",
    "                if val % tmp == 0: return False\n",
    "                tmp += 1\n",
    "            return True\n",
    "        def find(m):\n",
    "            h = (m + 1) // 2\n",
    "            v = 10 ** (h - 1)\n",
    "            while True:\n",
    "                tmp, ds = v, []\n",
    "                while tmp > 0:\n",
    "                    ds.append(tmp % 10)\n",
    "                    tmp //= 10\n",
    "                if len(ds) > h: return -1\n",
    "                val = v\n",
    "                for i in range(m % 2, h): val = 10 * val + ds[i]\n",
    "                if val >= n and test(val): return val\n",
    "                v += 1\n",
    "        cnt, tmp = 0, n\n",
    "        while tmp > 0:\n",
    "            cnt += 1\n",
    "            tmp //= 10\n",
    "        while True:\n",
    "            ret = find(cnt)\n",
    "            if ret != -1: return ret\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def is_prime(num):\n",
    "            return num > 1 and all(num % d != 0 for d in range(2, int(num**0.5) + 1))\n",
    "        def reverse(x):\n",
    "            res = 0\n",
    "            while x:\n",
    "                res = 10 * res + x % 10\n",
    "                x //= 10\n",
    "            return res\n",
    "        while True:\n",
    "            if n == reverse(n) and is_prime(n):\n",
    "                return n\n",
    "            n += 1\n",
    "            if 10**7 < n < 10**8:\n",
    "                n = 10**8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "\n",
    "        # 判断是否是素数\n",
    "        def is_prime(n):\n",
    "            return n > 1 and all(n % x for x in range(2, int(n ** 0.5) + 1))\n",
    "\n",
    "        # 获取大于等于n的回文数\n",
    "        def find_p_larger_than_n(n):\n",
    "            s = str(n)\n",
    "            while True:\n",
    "                # 翻转n的前半段，组合成回文数（偶数位就直接是前半段折半，奇数位对称中点折半）\n",
    "                # 例如：5432 -> 5445；54321 -> 54345\n",
    "                # 如果得到的数小于N，则把N的前半段加一，再翻转\n",
    "                # 这样翻转，一定是从N开始最小的回文数字开始遍历的\n",
    "                mid = len(s) // 2\n",
    "                first_half = s[:mid]\n",
    "                second_half = first_half[::-1] # 前半段翻转\n",
    "                # 最终回文字符串=原字符串前半段（可能还包含一个中点数）+翻转前半段得到的后半段\n",
    "                first_half_with_mid = s[:len(s)-len(second_half)]\n",
    "                final = first_half_with_mid + second_half\n",
    "                \n",
    "                # 翻转前半部分，和后半部组合成的新数字，如果满足大于n的条件，就退出\n",
    "                if int(final) >= n:\n",
    "                    return int(final)\n",
    "                \n",
    "                # 如果比n小，需要前半段+1，再翻转\n",
    "                first_half_with_mid_str = str(int(first_half_with_mid) + 1)\n",
    "                s = first_half_with_mid_str + second_half\n",
    "                \n",
    "        while True:\n",
    "            n = find_p_larger_than_n(n)\n",
    "            if is_prime(n):\n",
    "                return n\n",
    "            n += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(num):\n",
    "    s = str(num)\n",
    "    left, right = 0 ,len(s)-1\n",
    "    while(left < right):\n",
    "        if(s[left] != s[right]):\n",
    "            return False\n",
    "        left += 1\n",
    "        right -= 1\n",
    "    return True\n",
    "def isPrime(num):\n",
    "    if(num == 1):\n",
    "        return False\n",
    "    if(num == 2):\n",
    "        return True\n",
    "    x = 2\n",
    "    while(x*x <= num):\n",
    "        if(num % x == 0):\n",
    "            return False\n",
    "        x += 1\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        x = n \n",
    "        while(x <= 2*10**8):\n",
    "            if(check(x) and isPrime(x)):\n",
    "                return x\n",
    "            x += 1\n",
    "            if 10**7 < x < 10**8:\n",
    "                x = 10**8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 2\n",
    "        while True:\n",
    "            s = str(n)\n",
    "            l = len(s)\n",
    "            if l%2 == 0 and l > 2:\n",
    "                n = 10**(l)\n",
    "                continue\n",
    "            if n > 10 and s[0] in ['2','4','6','8']:\n",
    "                n = (int(s[0])+1)*10**(l-1)\n",
    "                continue\n",
    "            if s != s[::-1]:\n",
    "                n += 1\n",
    "                continue\n",
    "            for i in range(2,int(n**0.5)+1):\n",
    "                if n % i == 0:\n",
    "                    n += 1\n",
    "                    break\n",
    "            else:\n",
    "                return n\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "                \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def isPrime(n):  \n",
    "\n",
    "            if n <= 1:  \n",
    "\n",
    "                return False \n",
    "\n",
    "            i = 2 \n",
    "\n",
    "            while i*i <= n:  \n",
    "\n",
    "                if n % i == 0:  \n",
    "\n",
    "                    return False \n",
    "\n",
    "                i += 1 \n",
    "\n",
    "            return True \n",
    "            \n",
    "        if n<12:\n",
    "            return min([x if x>=n else 11 for x in[2,3,5,7,11]])\n",
    "        \n",
    "        l=len(str(n))\n",
    "        n0=str(n)[0]\n",
    "        if 1%2==0:\n",
    "            n=(10**l)+1\n",
    "        f=10**(l-1)\n",
    "        if n0 in ['4','5','6']:\n",
    "            n=7*f+7\n",
    "        elif n0=='2':\n",
    "            n=3*f+3\n",
    "        elif n0=='8':\n",
    "            n=9*f+9\n",
    "        t0=10**(l//2)\n",
    "        p=n//t0\n",
    "        while 1:\n",
    "            ns0=str(p)\n",
    "            \n",
    "            ns1=ns0[::-1][1:]\n",
    "            ns=int(ns0+ns1)\n",
    "            if not isPrime(ns) or ns<n:\n",
    "                p=p+1\n",
    "                \n",
    "                while 1:\n",
    "                    n0=str(p)[0]\n",
    "                    if n0 not in ['2','4','5','6','8']:\n",
    "                        break\n",
    "                    else:\n",
    "                        p+=1\n",
    "                        \n",
    "            else:\n",
    "                return ns\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def primePalindrome(self, N):\n",
    "        def is_prime(n):\n",
    "            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))\n",
    "\n",
    "        for length in range(1, 6):\n",
    "            #Check for odd-length palindromes\n",
    "            for root in range(10**(length - 1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-2::-1]) #eg. s = '123' to x = int('12321')\n",
    "                if x >= N and is_prime(x):\n",
    "                    return x\n",
    "                    #If we didn't check for even-length palindromes:\n",
    "                    #return min(x, 11) if N <= 11 else x\n",
    "\n",
    "            #Check for even-length palindromes\n",
    "            for root in range(10**(length - 1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-1::-1]) #eg. s = '123' to x = int('123321')\n",
    "                if x >= N and is_prime(x):\n",
    "                    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def is_prime(x):\n",
    "            for i in range(2,int(sqrt(x)) + 1):\n",
    "                if x % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        i = max(2,n)\n",
    "        while True:\n",
    "            if str(i) == str(i)[::-1] and is_prime(i):\n",
    "                return i\n",
    "            i += 1\n",
    "            if 10**7 < i < 10**8:\n",
    "                i = 10**8\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def reverse(x):\n",
    "            ans=0\n",
    "            while x:\n",
    "                ans=ans*10+x%10\n",
    "                x//=10\n",
    "            return ans\n",
    "        def isPrime(x):\n",
    "            if x==1: return False\n",
    "            for i in range(2,int(x**.5+1)):\n",
    "                if x%i ==0:\n",
    "                    return False\n",
    "            return True\n",
    "  \n",
    "        while 1:\n",
    "            if n==reverse(n) and isPrime(n):\n",
    "                return n\n",
    "            n=n+1\n",
    "            if 10**7 < n < 10**8:\n",
    "                n=10**8\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def is_prime(x):\n",
    "            if x == 1: return False\n",
    "            for i in range(2, int(x ** 0.5) + 1):\n",
    "                if x % i == 0: return False\n",
    "            return True\n",
    "\n",
    "        i = n\n",
    "        while True:\n",
    "            s = str(i)\n",
    "            if s[: len(s) // 2] == s[(len(s) + 1) // 2:][::-1] and is_prime(i):\n",
    "                return i\n",
    "            i += 1\n",
    "            if 10 ** 7 <= i < 10 ** 8:\n",
    "                i = 10 ** 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def isPrime(n):  \n",
    "\n",
    "            if n <= 1:  \n",
    "\n",
    "                return False \n",
    "\n",
    "            i = 2 \n",
    "\n",
    "            while i*i <= n:  \n",
    "\n",
    "                if n % i == 0:  \n",
    "\n",
    "                    return False \n",
    "\n",
    "                i += 1 \n",
    "\n",
    "            return True \n",
    "            \n",
    "        if n<12:\n",
    "            return min([x if x>=n else 11 for x in[2,3,5,7,11]])\n",
    "        \n",
    "        l=len(str(n))\n",
    "        if 1%2==0:\n",
    "            n=(10**l)+1\n",
    "        \n",
    "        t0=10**(l//2)\n",
    "        p=n//t0\n",
    "        while 1:\n",
    "            ns0=str(p)\n",
    "            ns1=ns0[::-1][1:]\n",
    "            ns=int(ns0+ns1)\n",
    "            if not isPrime(ns) or ns<n:\n",
    "                p=p+1\n",
    "            else:\n",
    "                return ns\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def next_Palindrome(n):\n",
    "            num=list(str(n))\n",
    "            m=len(num)\n",
    "            t=m//2\n",
    "            if m%2==0:\n",
    "                if int(\"\".join((num[:t]+num[:t][::-1])))>=n:\n",
    "                    return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                else:\n",
    "                    if int(num[t-1])<9:\n",
    "                        num[t-1]=str(int(num[t-1])+1)\n",
    "                        return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                    else:\n",
    "                        num[t-1]=str(0)\n",
    "                        x=t-2\n",
    "                        while x>=0:\n",
    "                            if int(num[x])<9:\n",
    "                                num[x]=str(int(num[x])+1)\n",
    "                                return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                            else:\n",
    "                                num[x]=str(0)\n",
    "                                x=x-1\n",
    "            else:\n",
    "                if int(\"\".join(num[:t+1]+num[:t][::-1]))>=n:\n",
    "                    return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                else:\n",
    "                    if int(num[t])<9:\n",
    "                        num[t]=str(int(num[t])+1)\n",
    "                        return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                    else:\n",
    "                        num[t]=\"0\"\n",
    "                        x=t-1\n",
    "                        while x>=0:\n",
    "                            if int(num[x])<9:\n",
    "                                num[x]=str(int(num[x])+1)\n",
    "                                return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                            else:\n",
    "                                num[x]=str(0)\n",
    "                                x=x-1\n",
    "        import math\n",
    "        def is_prime(n):\n",
    "            if n==1 or n==0:\n",
    "                return False\n",
    "            if n==2:\n",
    "                return True\n",
    "            for i in range(2,int(math.sqrt(n)+2)):\n",
    "                if n%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        next=next_Palindrome(n)\n",
    "        while not is_prime(next):\n",
    "            next=next_Palindrome(next+1)\n",
    "        return next\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        x = n \n",
    "        arr = [x for x in str(n)]\n",
    "        l = len(arr) \n",
    "        x = 0 \n",
    "        for i in range(l//2):\n",
    "            x = x * 10 + int(arr[i])  \n",
    "        ans = []\n",
    "        def isp(x):\n",
    "            if x == 1:\n",
    "                return False \n",
    "            for i in range(2, int(math.sqrt(x))+1):\n",
    "                if x % i == 0:\n",
    "                    return False \n",
    "            return True \n",
    "            \n",
    "        while x < 20000:\n",
    "            a = [y for y in str(x)]  \n",
    "            a1 = a + a[::-1][1:]\n",
    "            a2 = a + a[::-1]\n",
    "            x1 = int(''.join(a1))\n",
    "            x2 = int(''.join(a2))\n",
    "            if x1 >= n and isp(x1):\n",
    "                ans.append(x1) \n",
    "                break \n",
    "            if x2 >= n and isp(x2):\n",
    "                ans.append(x2) \n",
    "            if len(str(x+1)) > len(str(x)) and len(ans):\n",
    "                break \n",
    "            x+=1 \n",
    "        ans.sort() \n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def primePalindrome(self, n: int) -> int:\r\n",
    "        def is_prime(x: int) -> bool:\r\n",
    "            if x < 2:\r\n",
    "                return False \r\n",
    "            for i in range(2, isqrt(x) + 1):\r\n",
    "                if x % i == 0:\r\n",
    "                    return False \r\n",
    "            return True \r\n",
    "\r\n",
    "        for l in range(1, 6):\r\n",
    "            if l * 2 < len(str(n)):continue\r\n",
    "            for root in range(10 ** (l - 1), 10 ** l):\r\n",
    "                s = str(root)\r\n",
    "                x = int(s + s[-2::-1])\r\n",
    "                if x >= n and is_prime(x):\r\n",
    "                    return x \r\n",
    "            for root in range(10 ** (l - 1), 10 ** l):\r\n",
    "                s = str(root)\r\n",
    "                x = int(s + s[::-1])\r\n",
    "\r\n",
    "                if x >= n and is_prime(x):\r\n",
    "                    return x\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def judge(num):\n",
    "    if num==1:\n",
    "        return False\n",
    "    for i in range(2,int((num)**0.5)+1):\n",
    "        if num%i==0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def isreverse(num):\n",
    "    nums = []\n",
    "    while(num>0):\n",
    "        shu = num%10\n",
    "        nums.append(shu)\n",
    "        num = num//10\n",
    "    l=0\n",
    "    r=len(nums)-1\n",
    "    while l<=r:\n",
    "        if nums[l]!=nums[r]:\n",
    "            return False\n",
    "        l+=1\n",
    "        r-=1\n",
    "    return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        for i in range(1,6):\n",
    "            for j in range(10**(i-1),10**(i)):\n",
    "                num = str(j)\n",
    "                res = int(num+num[-2::-1])\n",
    "                if res>=n and judge(res):\n",
    "                    return res\n",
    "            for j in range(10**(i-1),10**(i)):\n",
    "                num = str(j)\n",
    "                res = int(num+num[-1::-1])\n",
    "                if res>=n and judge(res):\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def check(num):\n",
    "            return num > 1 and all(num%d for d in range(2,int(sqrt(num))+1))\n",
    "        def rev(x):\n",
    "            res = 0\n",
    "            while x:\n",
    "                res = 10*res+x%10\n",
    "                x //= 10\n",
    "            return res\n",
    "        i = int(sqrt(n))\n",
    "        while True:\n",
    "            if n == rev(n) and check(n):\n",
    "                return n \n",
    "            n += 1\n",
    "            if 10**7 < n < 10**8: n = 10**8\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def primePalindrome(self, n: int) -> int:\r\n",
    "\r\n",
    "        # def is_prime(x, add=False):\r\n",
    "        #     if x==1: return False\r\n",
    "        #     for i in range(len(primes)):\r\n",
    "        #         if x%primes[i] == 0:\r\n",
    "        #             return False\r\n",
    "        #         if primes[i]**2>x:\r\n",
    "        #             break\r\n",
    "        #     if add:\r\n",
    "        #         primes.append(x)\r\n",
    "        #     return True\r\n",
    "        # for i in range(3, 10^4):\r\n",
    "        #     is_prime(i, True)\r\n",
    "\r\n",
    "        def get_next_re(x):\r\n",
    "            xs = str(x)\r\n",
    "            l = (len(xs)+1)//2\r\n",
    "            left = int(xs[:l])\r\n",
    "            if xs[l-1::-1] <= xs[len(xs)//2:]:\r\n",
    "                left =left + 1\r\n",
    "            left = str(left)\r\n",
    "            if len(left) == l:\r\n",
    "                return int(left[:-1]+left[::-1]) if len(xs)%2 else int(left+left[::-1])\r\n",
    "            else:\r\n",
    "                return int(left[:-1]+left[l-1::-1]) if len(xs)%2 else int(left[:-1]+left[::-1])\r\n",
    "        def is_prime(x):\r\n",
    "            if x<3:\r\n",
    "                return True if x==2 else 0\r\n",
    "            m = 2\r\n",
    "            while m**2 <= x:\r\n",
    "                if x%m ==0:\r\n",
    "                    return False\r\n",
    "                else:\r\n",
    "                    m += 1\r\n",
    "            return True\r\n",
    "        def is_rec(x):\r\n",
    "            return str(x)==str(x)[::-1]\r\n",
    "        while not is_prime(n) or not is_rec(n):\r\n",
    "            n = get_next_re(n)\r\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def isPrime(n):  \n",
    "\n",
    "            if n <= 1:  \n",
    "\n",
    "                return False \n",
    "\n",
    "            i = 2 \n",
    "\n",
    "            while i*i <= n:  \n",
    "\n",
    "                if n % i == 0:  \n",
    "\n",
    "                    return False \n",
    "\n",
    "                i += 1 \n",
    "\n",
    "            return True \n",
    "            \n",
    "        if n<12:\n",
    "            return min([x if x>=n else 11 for x in[2,3,5,7,11]])\n",
    "        \n",
    "        l=len(str(n))\n",
    "        n0=str(n)[0]\n",
    "        if 1%2==0:\n",
    "            n=(10**l)+1\n",
    "        f=10**(l-1)\n",
    "        if n0 in ['4','5','6']:\n",
    "            n=7*f+7\n",
    "        elif n0=='2':\n",
    "            n=3*f+3\n",
    "        elif n0=='8':\n",
    "            n=9*f+9\n",
    "        t0=10**(l//2)\n",
    "        p=n//t0\n",
    "        while 1:\n",
    "            ns0=str(p)\n",
    "            \n",
    "            ns1=ns0[::-1][1:]\n",
    "            ns=int(ns0+ns1)\n",
    "            if not isPrime(ns) or ns<n:\n",
    "                p=p+1\n",
    "            else:\n",
    "                return ns\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def emumeratePalindrome(\n",
    "    minLength: int, maxLength: int, reverse=False\n",
    ") -> Generator[str, None, None]:\n",
    "    \"\"\"\n",
    "    遍历长度在 `[minLength, maxLength]` 之间的回文数字字符串.\n",
    "    maxLength <= 12.\n",
    "    \"\"\"\n",
    "    if minLength > maxLength:\n",
    "        return\n",
    "    if reverse:\n",
    "        for length in reversed(range(minLength, maxLength + 1)):\n",
    "            start = 10 ** ((length - 1) >> 1)\n",
    "            end = start * 10 - 1\n",
    "            for half in reversed(range(start, end + 1)):\n",
    "                if length & 1:\n",
    "                    yield f\"{half}{str(half)[:-1][::-1]}\"\n",
    "                else:\n",
    "                    yield f\"{half}{str(half)[::-1]}\"\n",
    "    else:\n",
    "        for length in range(minLength, maxLength + 1):\n",
    "            start = 10 ** ((length - 1) >> 1)\n",
    "            end = start * 10 - 1\n",
    "            for half in range(start, end + 1):\n",
    "                if length & 1:\n",
    "                    yield f\"{half}{str(half)[:-1][::-1]}\"\n",
    "                else:\n",
    "                    yield f\"{half}{str(half)[::-1]}\"\n",
    "\n",
    "\n",
    "\n",
    "def isPrime(n: int) -> bool:\n",
    "    return n >= 2 and all(n % i for i in range(2, int(n**0.5) + 1))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        求出大于或等于 N 的最小回文素数。\n",
    "        1 <= N <= 10^8\n",
    "        \"\"\"\n",
    "\n",
    "        for p in emumeratePalindrome(1, 9):\n",
    "            p = int(p)\n",
    "            if p < n:\n",
    "                continue\n",
    "            if isPrime(p):\n",
    "                return p\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isSS(a):\n",
    "            for i in range(2,int(a**0.5)+1):\n",
    "                if a%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def isHW(a):\n",
    "            return str(a)==str(a)[::-1]\n",
    "        \n",
    "        if n==1:\n",
    "            return 2\n",
    "\n",
    "        ans=n\n",
    "        while True:\n",
    "            if isHW(ans):\n",
    "                if isSS(ans):\n",
    "                    return ans\n",
    "            ans+=1\n",
    "            if 10**7 < ans < 10**8:\n",
    "                ans = 10**8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pre=[]\n",
    "def check(x):\n",
    "    if x==1:\n",
    "        return False\n",
    "    if x==2:\n",
    "        return True\n",
    "    j=(int)(sqrt(x))+1\n",
    "    for i in range(2,j+1):\n",
    "        if x%i==0:\n",
    "            return False\n",
    "    return True\n",
    "for i in range(1,20000):\n",
    "    if i<10 and check(i):\n",
    "        pre.append(i)\n",
    "    s=str(i)\n",
    "    s0=s+s[::-1]\n",
    "    temp0=int(s0)\n",
    "    s1=s+s[-2::-1]\n",
    "    temp1=int(s1)\n",
    "    if temp1>200000000:\n",
    "        break\n",
    "\n",
    "    if temp0<=200000000 and check(temp0):\n",
    "        pre.append(temp0)\n",
    "    if temp1<=200000000 and check(temp1):\n",
    "        pre.append(temp1)\n",
    "pre.sort()\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        return pre[bisect_left(pre,n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def is_prime(x):\n",
    "            if x == 1: return False\n",
    "            d = 2\n",
    "            while d * d <= x:\n",
    "                if x % d == 0: return False\n",
    "                d += 1\n",
    "            return True\n",
    "\n",
    "        i = n\n",
    "        while True:\n",
    "            s = str(i)\n",
    "            if s[: len(s) // 2] == s[(len(s) + 1) // 2:][::-1] and is_prime(i):\n",
    "                return i\n",
    "            i += 1\n",
    "            if 10 ** 7 <= i < 10 ** 8:\n",
    "                i = 10 ** 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isSS(a):\n",
    "            for i in range(2,int(a**0.5)+1):\n",
    "                if a%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def isHW(a):\n",
    "            return str(a)==str(a)[::-1]\n",
    "        \n",
    "        if n==1:\n",
    "            return 2\n",
    "\n",
    "        ans=n\n",
    "        while True:\n",
    "            if isHW(ans):\n",
    "                if isSS(ans):\n",
    "                    return ans\n",
    "            ans+=1\n",
    "            if 10**7 < ans < 10**8:\n",
    "                ans = 10**8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "import math \n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        while True:\n",
    "            if self.is_sole(n) and self.is_hui(n):\n",
    "                return n\n",
    "            else:\n",
    "                n += 1\n",
    "            if 10 ** 7 < n < 10 ** 8:\n",
    "                n = 10**8\n",
    "\n",
    "    def is_sole(self, n):\n",
    "        if n == 1:\n",
    "            return False\n",
    "        if n == 2:\n",
    "            return True\n",
    "        if n % 2 == 0:\n",
    "            return False\n",
    "        for i in range(3,int(math.sqrt(n)) + 1, 2):\n",
    "            if n % i == 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def is_hui(self, n):\n",
    "        s = str(n)\n",
    "        sl = len(s)\n",
    "        for i in range(int(sl / 2)):\n",
    "            if s[i] != s[sl - 1 - i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        for i in range(2,100000):\n",
    "            if str(i) == str(i)[::-1] and i >= n:\n",
    "                t = False\n",
    "                for j in range(2, int(math.sqrt(i)) + 1):\n",
    "                    if i % j == 0:\n",
    "                        t = True\n",
    "                        break\n",
    "                if not t:\n",
    "                    return i\n",
    "        for i in range(2, 100000):\n",
    "            tmp = int(str(i) + str(i)[::-1])\n",
    "            if int(str(i) + str(i)[::-1]) >= n:\n",
    "                t = False\n",
    "                for j in range(2, int(math.sqrt(tmp)) + 1):\n",
    "                    if tmp % j == 0:\n",
    "                        t = True\n",
    "                        break\n",
    "                if not t:\n",
    "                    return tmp\n",
    "            for z in range(10):\n",
    "                tmp1 = int(str(i) + str(z) + str(i)[::-1])\n",
    "                if tmp1 >= n:\n",
    "                    t = False\n",
    "                    for j in range(2,int(math.sqrt(tmp1)) + 1):\n",
    "                        if tmp1 % j == 0:\n",
    "                            t = True\n",
    "                            break\n",
    "                    if not t:\n",
    "                        return tmp1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def su(x):\n",
    "            if x in [2,3,5,7]:\n",
    "                return True\n",
    "            if x in [1,4,6,8,9]:\n",
    "                return False\n",
    "            for i in range(2,int(x**0.5)+1):\n",
    "                if x%i==0:\n",
    "                    return False\n",
    "            return True \n",
    "        def huiwen(x):\n",
    "            s1=str(x)\n",
    "            s2=list(s1)\n",
    "            s2.reverse()\n",
    "            s2=\"\".join(s2)\n",
    "            return s1==s2\n",
    "        while True:\n",
    "            if  huiwen(n) and su(n):\n",
    "                return n\n",
    "            n+=1\n",
    "            if 10**7<n<10**8:\n",
    "                n=10**8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isPrime(n):\n",
    "            if n<=1:\n",
    "                return False\n",
    "            for i in range(2, int(n**0.5)+1):\n",
    "                if n%i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        for length in range(1, 6):\n",
    "            for root in range(10**(length-1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-2::-1])\n",
    "                if x>=n and isPrime(x):\n",
    "                    return x\n",
    "            for root in range(10**(length-1), 10**length):\n",
    "                s = str(root)\n",
    "                x = int(s + s[-1::-1])\n",
    "                if x>=n and isPrime(x):\n",
    "                    return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def primePalindrome(self, n: int) -> int:\r\n",
    "        def is_prime(x):\r\n",
    "            if x<2:\r\n",
    "                return False\r\n",
    "            i=2\r\n",
    "            while i*i<=x:\r\n",
    "                if x%i==0:\r\n",
    "                    return False\r\n",
    "                i+=1\r\n",
    "            return True\r\n",
    "        \r\n",
    "        for l in range(len(str(n)),10):\r\n",
    "            half_l=(l+1)//2\r\n",
    "            # if \r\n",
    "            for i in range(10**(half_l-1),10**half_l):\r\n",
    "                r=str(i)\r\n",
    "                f=r+(r[-2::-1] if l&1 else r[::-1])\r\n",
    "                x=int(f)\r\n",
    "                if x>=n and is_prime(x):\r\n",
    "                    return x\r\n",
    "            \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        \n",
    "        def isPrime(n):  \n",
    "\n",
    "            if n <= 1:  \n",
    "\n",
    "                return False \n",
    "\n",
    "            i = 2 \n",
    "\n",
    "            while i*i <= n:  \n",
    "\n",
    "                if n % i == 0:  \n",
    "\n",
    "                    return False \n",
    "\n",
    "                i += 1 \n",
    "\n",
    "            return True \n",
    "            \n",
    "        if n<12:\n",
    "            return min([x if x>=n else 11 for x in[2,3,5,7,11]])\n",
    "        elif n<102:\n",
    "            return 101\n",
    "        \n",
    "        l=len(str(n))\n",
    "        n0=str(n)[0]\n",
    "        if 1%2==0:\n",
    "            n=(10**l)+1\n",
    "        f=10**(l-1)\n",
    "        if n0 in ['4','5','6']:\n",
    "            n=7*f+7\n",
    "        elif n0=='2':\n",
    "            n=3*f+3\n",
    "        elif n0=='8':\n",
    "            n=9*f+9\n",
    "        t0=10**(l//2)\n",
    "        p=n//t0\n",
    "        while 1:\n",
    "            #print(p)\n",
    "            ns0=str(p)\n",
    "            \n",
    "            ns1=ns0[::-1][1:]\n",
    "            ns=int(ns0+ns1)\n",
    "            if not isPrime(ns) or ns<n:\n",
    "                p=p+1\n",
    "                \n",
    "                while 1:\n",
    "                    n0=str(p)[0]\n",
    "                    f=10**(len(str(p))-1)\n",
    "                    if n0 not in ['2','4','5','6','8']:\n",
    "                        break\n",
    "                    elif n0 =='2':\n",
    "                        p=3*f\n",
    "                    elif n0 =='8':\n",
    "                        p=9*f\n",
    "                    else:\n",
    "                        p=7*f\n",
    "                        \n",
    "                       \n",
    "                        \n",
    "            else:\n",
    "                return ns\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def is_prime(n: int) -> bool:\n",
    "    \"\"\"returns True if n is prime else False\"\"\"\n",
    "    if n < 5 or n & 1 == 0 or n % 3 == 0:\n",
    "        return 2 <= n <= 3\n",
    "    s = ((n - 1) & (1 - n)).bit_length() - 1\n",
    "    d = n >> s\n",
    "    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:\n",
    "        p = pow(a, d, n)\n",
    "        if p == 1 or p == n - 1 or a % n == 0:\n",
    "            continue\n",
    "        for _ in range(s):\n",
    "            p = (p * p) % n\n",
    "            if p == n - 1:\n",
    "                break\n",
    "        else:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "\n",
    "        for length in range(1, 6):\n",
    "            for root in range(10 ** (length - 1), 10 ** length):\n",
    "                s = str(root)\n",
    "                num = int(s + s[-2::-1])\n",
    "                if num >= n and is_prime(num):\n",
    "                    return num\n",
    "            \n",
    "            for root in range(10 ** (length - 1), 10 ** length):\n",
    "                s = str(root)\n",
    "                num = int(s + s[::-1])\n",
    "                if num >= n and is_prime(num):\n",
    "                    return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def isPrime(n):\n",
    "            if n < 2:\n",
    "                return False\n",
    "            for i in range(2, int(n**0.5) + 1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def isPalindrome(n):\n",
    "            str_n = str(n)\n",
    "            left, right = 0, len(str_n) - 1\n",
    "            while left <= right:\n",
    "                if str_n[left] != str_n[right]:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        \n",
    "        num = n\n",
    "        while True:\n",
    "            if isPalindrome(num) and isPrime(num):\n",
    "                return num\n",
    "            num += 1\n",
    "            if 10**7 < num < 10**8:\n",
    "                num = 10**8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def next_Palindrome(n):\n",
    "            num=list(str(n))\n",
    "            m=len(num)\n",
    "            t=m//2\n",
    "            if m%2==0:\n",
    "                if int(\"\".join((num[:t]+num[:t][::-1])))>=n:\n",
    "                    return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                else:\n",
    "                    if int(num[t-1])<9:\n",
    "                        num[t-1]=str(int(num[t-1])+1)\n",
    "                        return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                    else:\n",
    "                        num[t-1]=str(0)\n",
    "                        x=t-2\n",
    "                        while x>=0:\n",
    "                            if int(num[x])<9:\n",
    "                                num[x]=str(int(num[x])+1)\n",
    "                                return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                            else:\n",
    "                                num[x]=str(0)\n",
    "                                x=x-1\n",
    "            else:\n",
    "                if int(\"\".join(num[:t+1]+num[:t][::-1]))>=n:\n",
    "                    return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                else:\n",
    "                    if int(num[t])<9:\n",
    "                        num[t]=str(int(num[t])+1)\n",
    "                        return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                    else:\n",
    "                        num[t]=\"0\"\n",
    "                        x=t-1\n",
    "                        while x>=0:\n",
    "                            if int(num[x])<9:\n",
    "                                num[x]=str(int(num[x])+1)\n",
    "                                return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                            else:\n",
    "                                num[x]=str(0)\n",
    "                                x=x-1\n",
    "        import math\n",
    "        def is_prime(n):\n",
    "            if n==1 or n==0:\n",
    "                return False\n",
    "            if n==2:\n",
    "                return True\n",
    "            for i in range(2,int(math.sqrt(n)+1)):\n",
    "                if n%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        next=next_Palindrome(n)\n",
    "        while not is_prime(next):\n",
    "            next=next_Palindrome(next+1)\n",
    "        return next\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def next_Palindrome(n):\n",
    "            num=list(str(n))\n",
    "            m=len(num)\n",
    "            t=m//2\n",
    "            if m%2==0:\n",
    "                if int(\"\".join((num[:t]+num[:t][::-1])))>=n:\n",
    "                    return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                else:\n",
    "                    if int(num[t-1])<9:\n",
    "                        num[t-1]=str(int(num[t-1])+1)\n",
    "                        return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                    else:\n",
    "                        num[t-1]=str(0)\n",
    "                        x=t-2\n",
    "                        while x>=0:\n",
    "                            if int(num[x])<9:\n",
    "                                num[x]=str(int(num[x])+1)\n",
    "                                return int(\"\".join((num[:t]+num[:t][::-1])))\n",
    "                            else:\n",
    "                                num[x]=str(0)\n",
    "                                x=x-1\n",
    "            else:\n",
    "                if int(\"\".join(num[:t+1]+num[:t][::-1]))>=n:\n",
    "                    return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                else:\n",
    "                    if int(num[t])<9:\n",
    "                        num[t]=str(int(num[t])+1)\n",
    "                        return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                    else:\n",
    "                        num[t]=\"0\"\n",
    "                        x=t-1\n",
    "                        while x>=0:\n",
    "                            if int(num[x])<9:\n",
    "                                num[x]=str(int(num[x])+1)\n",
    "                                return int(\"\".join(num[:t+1]+num[:t][::-1]))\n",
    "                            else:\n",
    "                                num[x]=str(0)\n",
    "                                x=x-1\n",
    "        import math\n",
    "        def is_prime(n):\n",
    "            if n==1 or n==0:\n",
    "                return False\n",
    "            if n==2:\n",
    "                return True\n",
    "            for i in range(2,int(math.sqrt(n))+1):\n",
    "                if n%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        next=next_Palindrome(n)\n",
    "        while not is_prime(next):\n",
    "            next=next_Palindrome(next+1)\n",
    "        return next\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        def IsPrime(n: int) -> bool:\n",
    "            return n > 1 and all([n % mod for mod in range(2, int(n ** .5) + 1)])\n",
    "\n",
    "        def Reverse(n: int) -> int:\n",
    "            ans = 0\n",
    "            while n != 0:\n",
    "                ans = ans * 10 + n % 10\n",
    "                n = n // 10\n",
    "\n",
    "            return ans\n",
    "\n",
    "        while n != Reverse(n) or not IsPrime(n):\n",
    "            n += 1\n",
    "            if 10**7 < n < 10**8:\n",
    "                n = 10**8\n",
    "\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        #return 6\n",
    "        N=n\n",
    "        def is_prime(n):\n",
    "            return n>1 and all([n%i for i in range(2,int(n**0.5)+1)])\n",
    "            #return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))\n",
    "\n",
    "        def reverse(x):\n",
    "            ans = 0\n",
    "            while x>0:\n",
    "                ans = 10 * ans + x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "\n",
    "        while True:\n",
    "            if N == reverse(N) and is_prime(N):\n",
    "                return N\n",
    "            N += 1\n",
    "            if 10**7 < N < 10**8:\n",
    "                N = 10**8\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 6步进判别法\n",
    "def is_prime(n):\n",
    "    # 6x,6x+2,6x+3,6x+4\n",
    "    # 6x+1和6x+5才可能是素数\n",
    "    if n < 6:\n",
    "        return n > 1 and all([n%i for i in range(2, int(n**0.5) + 1)])\n",
    "    \n",
    "    if (n % 6 == 1) or (n % 6 == 5):\n",
    "        return n > 1 and all([n%i for i in range(2, int(n**0.5) + 1)])\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def is_palindrome(text):\n",
    "    return (text == text[::-1])\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        while True:\n",
    "\n",
    "            # 不是回文则跳过\n",
    "            if is_palindrome(str(n)):\n",
    "                # 是回文但是\n",
    "                # 大于11且长度为偶数时必定不为素数,跳过\n",
    "                if n > 11 and (len(str(n)) % 2 == 0):\n",
    "                    n = 10**(len(str(n)))\n",
    "                    continue\n",
    "\n",
    "                if is_prime(n):\n",
    "                    break\n",
    "            n += 1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res=[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821, 1300031, 1303031, 1311131, 1317131, 1327231, 1328231, 1333331, 1335331, 1338331, 1343431, 1360631, 1362631, 1363631, 1371731, 1374731, 1390931, 1407041, 1409041, 1411141, 1412141, 1422241, 1437341, 1444441, 1447441, 1452541, 1456541, 1461641, 1463641, 1464641, 1469641, 1486841, 1489841, 1490941, 1496941, 1508051, 1513151, 1520251, 1532351, 1535351, 1542451, 1548451, 1550551, 1551551, 1556551, 1557551, 1565651, 1572751, 1579751, 1580851, 1583851, 1589851, 1594951, 1597951, 1598951, 1600061, 1609061, 1611161, 1616161, 1628261, 1630361, 1633361, 1640461, 1643461, 1646461, 1654561, 1657561, 1658561, 1660661, 1670761, 1684861, 1685861, 1688861, 1695961, 1703071, 1707071, 1712171, 1714171, 1730371, 1734371, 1737371, 1748471, 1755571, 1761671, 1764671, 1777771, 1793971, 1802081, 1805081, 1820281, 1823281, 1824281, 1826281, 1829281, 1831381, 1832381, 1842481, 1851581, 1853581, 1856581, 1865681, 1876781, 1878781, 1879781, 1880881, 1881881, 1883881, 1884881, 1895981, 1903091, 1908091, 1909091, 1917191, 1924291, 1930391, 1936391, 1941491, 1951591, 1952591, 1957591, 1958591, 1963691, 1968691, 1969691, 1970791, 1976791, 1981891, 1982891, 1984891, 1987891, 1988891, 1993991, 1995991, 1998991, 3001003, 3002003, 3007003, 3016103, 3026203, 3064603, 3065603, 3072703, 3073703, 3075703, 3083803, 3089803, 3091903, 3095903, 3103013, 3106013, 3127213, 3135313, 3140413, 3155513, 3158513, 3160613, 3166613, 3181813, 3187813, 3193913, 3196913, 3198913, 3211123, 3212123, 3218123, 3222223, 3223223, 3228223, 3233323, 3236323, 3241423, 3245423, 3252523, 3256523, 3258523, 3260623, 3267623, 3272723, 3283823, 3285823, 3286823, 3288823, 3291923, 3293923, 3304033, 3305033, 3307033, 3310133, 3315133, 3319133, 3321233, 3329233, 3331333, 3337333, 3343433, 3353533, 3362633, 3364633, 3365633, 3368633, 3380833, 3391933, 3392933, 3400043, 3411143, 3417143, 3424243, 3425243, 3427243, 3439343, 3441443, 3443443, 3444443, 3447443, 3449443, 3452543, 3460643, 3466643, 3470743, 3479743, 3485843, 3487843, 3503053, 3515153, 3517153, 3528253, 3541453, 3553553, 3558553, 3563653, 3569653, 3586853, 3589853, 3590953, 3591953, 3594953, 3601063, 3607063, 3618163, 3621263, 3627263, 3635363, 3643463, 3646463, 3670763, 3673763, 3680863, 3689863, 3698963, 3708073, 3709073, 3716173, 3717173, 3721273, 3722273, 3728273, 3732373, 3743473, 3746473, 3762673, 3763673, 3765673, 3768673, 3769673, 3773773, 3774773, 3781873, 3784873, 3792973, 3793973, 3799973, 3804083, 3806083, 3812183, 3814183, 3826283, 3829283, 3836383, 3842483, 3853583, 3858583, 3863683, 3864683, 3867683, 3869683, 3871783, 3878783, 3893983, 3899983, 3913193, 3916193, 3918193, 3924293, 3927293, 3931393, 3938393, 3942493, 3946493, 3948493, 3964693, 3970793, 3983893, 3991993, 3994993, 3997993, 3998993, 7014107, 7035307, 7036307, 7041407, 7046407, 7057507, 7065607, 7069607, 7073707, 7079707, 7082807, 7084807, 7087807, 7093907, 7096907, 7100017, 7114117, 7115117, 7118117, 7129217, 7134317, 7136317, 7141417, 7145417, 7155517, 7156517, 7158517, 7159517, 7177717, 7190917, 7194917, 7215127, 7226227, 7246427, 7249427, 7250527, 7256527, 7257527, 7261627, 7267627, 7276727, 7278727, 7291927, 7300037, 7302037, 7310137, 7314137, 7324237, 7327237, 7347437, 7352537, 7354537, 7362637, 7365637, 7381837, 7388837, 7392937, 7401047, 7403047, 7409047, 7415147, 7434347, 7436347, 7439347, 7452547, 7461647, 7466647, 7472747, 7475747, 7485847, 7486847, 7489847, 7493947, 7507057, 7508057, 7518157, 7519157, 7521257, 7527257, 7540457, 7562657, 7564657, 7576757, 7586857, 7592957, 7594957, 7600067, 7611167, 7619167, 7622267, 7630367, 7632367, 7644467, 7654567, 7662667, 7665667, 7666667, 7668667, 7669667, 7674767, 7681867, 7690967, 7693967, 7696967, 7715177, 7718177, 7722277, 7729277, 7733377, 7742477, 7747477, 7750577, 7758577, 7764677, 7772777, 7774777, 7778777, 7782877, 7783877, 7791977, 7794977, 7807087, 7819187, 7820287, 7821287, 7831387, 7832387, 7838387, 7843487, 7850587, 7856587, 7865687, 7867687, 7868687, 7873787, 7884887, 7891987, 7897987, 7913197, 7916197, 7930397, 7933397, 7935397, 7938397, 7941497, 7943497, 7949497, 7957597, 7958597, 7960697, 7977797, 7984897, 7985897, 7987897, 7996997, 9002009, 9015109, 9024209, 9037309, 9042409, 9043409, 9045409, 9046409, 9049409, 9067609, 9073709, 9076709, 9078709, 9091909, 9095909, 9103019, 9109019, 9110119, 9127219, 9128219, 9136319, 9149419, 9169619, 9173719, 9174719, 9179719, 9185819, 9196919, 9199919, 9200029, 9209029, 9212129, 9217129, 9222229, 9223229, 9230329, 9231329, 9255529, 9269629, 9271729, 9277729, 9280829, 9286829, 9289829, 9318139, 9320239, 9324239, 9329239, 9332339, 9338339, 9351539, 9357539, 9375739, 9384839, 9397939, 9400049, 9414149, 9419149, 9433349, 9439349, 9440449, 9446449, 9451549, 9470749, 9477749, 9492949, 9493949, 9495949, 9504059, 9514159, 9526259, 9529259, 9547459, 9556559, 9558559, 9561659, 9577759, 9583859, 9585859, 9586859, 9601069, 9602069, 9604069, 9610169, 9620269, 9624269, 9626269, 9632369, 9634369, 9645469, 9650569, 9657569, 9670769, 9686869, 9700079, 9709079, 9711179, 9714179, 9724279, 9727279, 9732379, 9733379, 9743479, 9749479, 9752579, 9754579, 9758579, 9762679, 9770779, 9776779, 9779779, 9781879, 9782879, 9787879, 9788879, 9795979, 9801089, 9807089, 9809089, 9817189, 9818189, 9820289, 9822289, 9836389, 9837389, 9845489, 9852589, 9871789, 9888889, 9889889, 9896989, 9902099, 9907099, 9908099, 9916199, 9918199, 9919199, 9921299, 9923299, 9926299, 9927299, 9931399, 9932399, 9935399, 9938399, 9957599, 9965699, 9978799, 9980899, 9981899, 9989899, 100030001, 100050001, 100060001, 100111001, 100131001, 100161001, 100404001, 100656001, 100707001, 100767001, 100888001, 100999001, 101030101, 101060101, 101141101, 101171101, 101282101, 101292101, 101343101, 101373101, 101414101, 101424101, 101474101, 101595101, 101616101, 101717101, 101777101, 101838101, 101898101, 101919101, 101949101, 101999101, 102040201, 102070201, 102202201, 102232201, 102272201, 102343201, 102383201, 102454201, 102484201, 102515201, 102676201, 102686201, 102707201, 102808201, 102838201, 103000301, 103060301, 103161301, 103212301, 103282301, 103303301, 103323301, 103333301, 103363301, 103464301, 103515301, 103575301, 103696301, 103777301, 103818301, 103828301, 103909301, 103939301, 104000401, 104030401, 104040401, 104111401, 104222401, 104282401, 104333401, 104585401, 104616401, 104787401, 104838401, 104919401, 104949401, 105121501, 105191501, 105202501, 105262501, 105272501, 105313501, 105323501, 105343501, 105575501, 105616501, 105656501, 105757501, 105818501, 105868501, 105929501, 106060601, 106111601, 106131601, 106191601, 106222601, 106272601, 106353601, 106444601, 106464601, 106545601, 106555601, 106717601, 106909601, 106929601, 107000701, 107070701, 107121701, 107232701, 107393701, 107414701, 107424701, 107595701, 107636701, 107646701, 107747701, 107757701, 107828701, 107858701, 107868701, 107888701, 107939701, 107949701, 108070801, 108101801, 108121801, 108151801, 108212801, 108323801, 108373801, 108383801, 108434801, 108464801, 108484801, 108494801, 108505801, 108565801, 108686801, 108707801, 108767801, 108838801, 108919801, 108959801, 109000901, 109101901, 109111901, 109161901, 109333901, 109404901, 109434901, 109444901, 109474901, 109575901, 109656901, 109747901, 109777901, 109797901, 109818901, 109909901, 109929901, 110111011, 110232011, 110252011, 110343011, 110424011, 110505011, 110565011, 110676011, 110747011, 110757011, 110909011, 110949011, 110999011, 111010111, 111020111, 111050111, 111070111, 111181111, 111191111, 111262111, 111272111, 111454111, 111484111, 111515111, 111616111, 111686111, 111757111, 111848111, 112030211, 112060211, 112111211, 112161211, 112171211, 112212211, 112434211, 112494211, 112545211, 112636211, 112878211, 112959211, 112969211, 112989211, 113030311, 113090311, 113111311, 113262311, 113282311, 113474311, 113535311, 113565311, 113616311, 113636311, 113888311, 113939311, 114040411, 114191411, 114232411, 114353411, 114383411, 114484411, 114494411, 114535411, 114727411, 114808411, 114818411, 114848411, 114878411, 114898411, 115000511, 115020511, 115060511, 115111511, 115141511, 115191511, 115212511, 115222511, 115404511, 115464511, 115545511, 115636511, 115737511, 115767511, 115797511, 115828511, 115959511, 116000611, 116010611, 116040611, 116424611, 116505611, 116646611, 116696611, 116757611, 116777611, 116828611, 116868611, 116919611, 117070711, 117101711, 117262711, 117272711, 117323711, 117484711, 117505711, 117515711, 117616711, 117686711, 117757711, 117767711, 117797711, 117818711, 117959711, 118252811, 118272811, 118414811, 118464811, 118525811, 118626811, 118686811, 118696811, 118717811, 118818811, 118848811, 118909811, 118959811, 119010911, 119171911, 119202911, 119343911, 119363911, 119454911, 119585911, 119595911, 119646911, 119676911, 119696911, 119717911, 119787911, 119868911, 119888911, 119969911, 120191021, 120242021, 120434021, 120454021, 120494021, 120535021, 120565021, 120646021, 120808021, 120868021, 120989021, 121080121, 121111121, 121131121, 121161121, 121272121, 121282121, 121393121, 121414121, 121555121, 121747121, 121818121, 121878121, 121939121, 121989121, 122040221, 122232221, 122262221, 122292221, 122333221, 122363221, 122373221, 122393221, 122444221, 122484221, 122535221, 122696221, 122787221, 122858221, 122919221, 123161321, 123292321, 123424321, 123484321, 123494321, 123575321, 123767321, 123838321, 123989321, 124000421, 124080421, 124101421, 124131421, 124252421, 124323421, 124333421, 124434421, 124515421, 124525421, 124626421, 124656421, 124717421, 124737421, 124959421, 124989421, 125000521, 125010521, 125232521, 125252521, 125292521, 125343521, 125474521, 125505521, 125565521, 125606521, 125616521, 125757521, 125838521, 125939521, 125979521, 125999521, 126101621, 126161621, 126181621, 126202621, 126212621, 126323621, 126424621, 126484621, 126535621, 126595621, 126616621, 126676621, 126686621, 126727621, 126737621, 126757621, 126878621, 127060721, 127090721, 127131721, 127212721, 127383721, 127494721, 127545721, 127636721, 127656721, 127686721, 127717721, 127747721, 127828721, 127909721, 127929721, 128070821, 128090821, 128121821, 128181821, 128202821, 128252821, 128262821, 128282821, 128444821, 128474821, 128525821, 128535821, 128595821, 128646821, 128747821, 128787821, 128868821, 128919821, 128939821, 129080921, 129202921, 129292921, 129323921, 129373921, 129484921, 129494921, 129535921, 129737921, 129919921, 129979921, 130020031, 130030031, 130060031, 130141031, 130171031, 130222031, 130333031, 130444031, 130464031, 130545031, 130555031, 130585031, 130606031, 130636031, 130717031, 130767031, 130818031, 130828031, 130858031, 130969031, 131030131, 131111131, 131121131, 131222131, 131252131, 131333131, 131555131, 131565131, 131585131, 131646131, 131676131, 131828131, 132010231, 132191231, 132464231, 132535231, 132595231, 132646231, 132676231, 132757231, 133020331, 133060331, 133111331, 133161331, 133252331, 133474331, 133494331, 133575331, 133686331, 133767331, 133818331, 133909331, 134090431, 134181431, 134232431, 134424431, 134505431, 134525431, 134535431, 134616431, 134757431, 134808431, 134858431, 134888431, 134909431, 134919431, 134979431, 135010531, 135040531, 135101531, 135121531, 135161531, 135262531, 135434531, 135494531, 135515531, 135626531, 135646531, 135707531, 135838531, 135868531, 135878531, 135929531, 135959531, 135979531, 136090631, 136171631, 136222631, 136252631, 136303631, 136363631, 136474631, 136545631, 136737631, 136797631, 136818631, 136909631, 136969631, 137030731, 137040731, 137060731, 137090731, 137151731, 137171731, 137232731, 137282731, 137333731, 137363731, 137424731, 137474731, 137606731, 137636731, 137696731, 137757731, 137808731, 137838731, 137939731, 137999731, 138040831, 138131831, 138242831, 138292831, 138313831, 138383831, 138454831, 138575831, 138616831, 138646831, 138757831, 138898831, 138959831, 138989831, 139131931, 139161931, 139222931, 139252931, 139282931, 139383931, 139474931, 139515931, 139606931, 139626931, 139717931, 139848931, 139959931, 139969931, 139999931, 140000041, 140030041, 140151041, 140303041, 140505041, 140565041, 140606041, 140777041, 140787041, 140828041, 140868041, 140898041, 141020141, 141070141, 141131141, 141151141, 141242141, 141262141, 141313141, 141343141, 141383141, 141484141, 141494141, 141575141, 141595141, 141616141, 141767141, 141787141, 141848141, 142000241, 142030241, 142080241, 142252241, 142272241, 142353241, 142363241, 142464241, 142545241, 142555241, 142686241, 142707241, 142797241, 142858241, 142888241, 143090341, 143181341, 143262341, 143303341, 143454341, 143474341, 143585341, 143636341, 143787341, 143828341, 143919341, 143969341, 144010441, 144020441, 144202441, 144212441, 144313441, 144353441, 144404441, 144434441, 144484441, 144505441, 144707441, 144757441, 144808441, 144818441, 144848441, 144878441, 144898441, 144979441, 144989441, 145020541, 145030541, 145090541, 145353541, 145363541, 145393541, 145464541, 145494541, 145575541, 145666541, 145767541, 146030641, 146040641, 146181641, 146222641, 146252641, 146313641, 146363641, 146505641, 146555641, 146565641, 146676641, 146858641, 146909641, 147191741, 147232741, 147242741, 147313741, 147343741, 147373741, 147434741, 147515741, 147565741, 147616741, 147686741, 147707741, 147757741, 147838741, 147929741, 148020841, 148060841, 148080841, 148414841, 148444841, 148525841, 148545841, 148585841, 148666841, 148686841, 148707841, 148818841, 148858841, 148888841, 148969841, 149000941, 149333941, 149343941, 149484941, 149535941, 149555941, 149616941, 149646941, 149696941, 149858941, 149888941, 149909941, 149919941, 149939941, 150070051, 150151051, 150181051, 150202051, 150272051, 150434051, 150494051, 150505051, 150626051, 150686051, 150727051, 150808051, 150818051, 150979051, 151080151, 151161151, 151212151, 151222151, 151282151, 151353151, 151545151, 151585151, 151656151, 151737151, 151777151, 151858151, 151878151, 151888151, 151959151, 151969151, 151999151, 152090251, 152111251, 152171251, 152181251, 152252251, 152363251, 152393251, 152454251, 152505251, 152565251, 152616251, 152646251, 152666251, 152696251, 152888251, 152939251, 153212351, 153272351, 153292351, 153313351, 153323351, 153404351, 153424351, 153454351, 153484351, 153494351, 153626351, 153808351, 153818351, 153838351, 153979351, 154030451, 154191451, 154252451, 154272451, 154303451, 154323451, 154383451, 154393451, 154474451, 154494451, 154555451, 154575451, 154989451, 155060551, 155141551, 155171551, 155292551, 155313551, 155333551, 155373551, 155424551, 155474551, 155535551, 155646551, 155666551, 155676551, 155808551, 155828551, 155868551, 156151651, 156262651, 156343651, 156424651, 156434651, 156494651, 156545651, 156595651, 156656651, 156707651, 156727651, 156757651, 156848651, 156878651, 156949651, 157090751, 157101751, 157161751, 157252751, 157393751, 157444751, 157555751, 157717751, 157878751, 157888751, 157939751, 157959751, 157989751, 158090851, 158111851, 158222851, 158252851, 158363851, 158474851, 158595851, 158676851, 158696851, 158747851, 158808851, 158858851, 158898851, 158909851, 159020951, 159040951, 159050951, 159121951, 159181951, 159191951, 159202951, 159232951, 159262951, 159292951, 159323951, 159404951, 159464951, 159565951, 159595951, 159646951, 159757951, 159808951, 159919951, 159929951, 159959951, 160020061, 160050061, 160080061, 160101061, 160131061, 160141061, 160161061, 160171061, 160393061, 160545061, 160696061, 160707061, 160717061, 160797061, 160878061, 161171161, 161282161, 161313161, 161363161, 161474161, 161484161, 161535161, 161585161, 161636161, 161787161, 161838161, 161969161, 162040261, 162232261, 162404261, 162464261, 162484261, 162565261, 162686261, 162707261, 162757261, 162898261, 162919261, 162949261, 162959261, 162979261, 162989261, 163101361, 163333361, 163434361, 163464361, 163474361, 163494361, 163515361, 163555361, 163606361, 163686361, 163696361, 163878361, 163959361, 164000461, 164070461, 164151461, 164292461, 164333461, 164454461, 164484461, 164585461, 164616461, 164696461, 164717461, 164727461, 164838461, 165101561, 165161561, 165191561, 165212561, 165343561, 165515561, 165535561, 165808561, 165878561, 165898561, 165919561, 165949561, 166000661, 166080661, 166171661, 166191661, 166404661, 166545661, 166555661, 166636661, 166686661, 166818661, 166828661, 166878661, 166888661, 166929661, 167000761, 167111761, 167262761, 167393761, 167454761, 167474761, 167484761, 167636761, 167646761, 167787761, 167888761, 167898761, 167979761, 168151861, 168191861, 168232861, 168404861, 168505861, 168515861, 168565861, 168818861, 168898861, 168929861, 168949861, 169060961, 169131961, 169141961, 169282961, 169333961, 169383961, 169464961, 169555961, 169606961, 169656961, 169666961, 169686961, 169777961, 169797961, 169858961, 169999961, 170040071, 170060071, 170232071, 170303071, 170333071, 170414071, 170424071, 170484071, 170606071, 170616071, 170646071, 170828071, 170838071, 170909071, 170979071, 171080171, 171262171, 171292171, 171343171, 171565171, 171575171, 171767171, 171919171, 171959171, 172060271, 172090271, 172161271, 172353271, 172363271, 172393271, 172474271, 172585271, 172656271, 172747271, 172767271, 172797271, 172878271, 172909271, 172959271, 173000371, 173030371, 173090371, 173252371, 173373371, 173454371, 173525371, 173585371, 173696371, 173757371, 173777371, 173828371, 173868371, 173888371, 173898371, 173919371, 174080471, 174121471, 174131471, 174181471, 174313471, 174343471, 174595471, 174646471, 174676471, 174919471, 174949471, 174979471, 174989471, 175000571, 175090571, 175101571, 175111571, 175353571, 175444571, 175555571, 175626571, 175747571, 175777571, 175848571, 175909571, 176090671, 176111671, 176141671, 176181671, 176232671, 176313671, 176333671, 176373671, 176393671, 176414671, 176585671, 176636671, 176646671, 176666671, 176696671, 176757671, 176787671, 176888671, 176898671, 176939671, 177121771, 177161771, 177202771, 177242771, 177323771, 177565771, 177616771, 177707771, 177757771, 177868771, 178101871, 178131871, 178141871, 178161871, 178353871, 178414871, 178515871, 178525871, 178656871, 178717871, 178747871, 178878871, 178969871, 178989871, 178999871, 179010971, 179060971, 179222971, 179232971, 179262971, 179414971, 179454971, 179484971, 179717971, 179777971, 179808971, 179858971, 179868971, 179909971, 179969971, 179999971, 180070081, 180101081, 180161081, 180292081, 180515081, 180535081, 180545081, 180565081, 180616081, 180757081, 180959081, 181111181, 181515181, 181545181, 181666181, 181737181, 181797181, 181888181, 182010281, 182202281, 182373281, 182585281, 182616281, 182636281, 182777281, 182858281, 182949281, 183232381, 183626381, 183656381, 183737381, 183898381, 183979381, 183989381, 184030481, 184212481, 184222481, 184303481, 184393481, 184414481, 184545481, 184585481, 184606481, 184636481, 184747481, 184818481, 184878481, 185232581, 185373581, 185393581, 185525581, 185555581, 185595581, 185676581, 185757581, 185838581, 185858581, 185868581, 185999581, 186010681, 186040681, 186050681, 186070681, 186101681, 186131681, 186151681, 186161681, 186424681, 186484681, 186505681, 186565681, 186656681, 186676681, 186787681, 186898681, 187090781, 187101781, 187111781, 187161781, 187272781, 187404781, 187434781, 187444781, 187525781, 187767781, 187909781, 187939781, 187999781, 188010881, 188060881, 188141881, 188151881, 188303881, 188373881, 188414881, 188454881, 188505881, 188525881, 188535881, 188616881, 188636881, 188646881, 188727881, 188777881, 188868881, 188888881, 188898881, 188979881, 189080981, 189131981, 189262981, 189292981, 189464981, 189535981, 189595981, 189727981, 189787981, 189838981, 189898981, 189929981, 190000091, 190020091, 190080091, 190101091, 190252091, 190404091, 190434091, 190464091, 190494091, 190656091, 190696091, 190717091, 190747091, 190777091, 190858091, 190909091, 191090191, 191171191, 191232191, 191292191, 191313191, 191565191, 191595191, 191727191, 191757191, 191838191, 191868191, 191939191, 191969191, 192101291, 192191291, 192202291, 192242291, 192313291, 192404291, 192454291, 192484291, 192767291, 192797291, 192898291, 193000391, 193030391, 193191391, 193212391, 193282391, 193303391, 193383391, 193414391, 193464391, 193555391, 193686391, 193858391, 193888391, 194000491, 194070491, 194121491, 194222491, 194232491, 194292491, 194303491, 194393491, 194505491, 194595491, 194606491, 194787491, 194939491, 194999491, 195010591, 195040591, 195070591, 195151591, 195202591, 195242591, 195353591, 195505591, 195545591, 195707591, 195767591, 195868591, 195878591, 195949591, 195979591, 196000691, 196090691, 196323691, 196333691, 196363691, 196696691, 196797691, 196828691, 196878691, 197030791, 197060791, 197070791, 197090791, 197111791, 197121791, 197202791, 197292791, 197343791, 197454791, 197525791, 197606791, 197616791, 197868791, 197898791, 197919791, 198040891, 198070891, 198080891, 198131891, 198292891, 198343891, 198353891, 198383891, 198454891, 198565891, 198656891, 198707891, 198787891, 198878891, 198919891, 199030991, 199080991, 199141991, 199171991, 199212991, 199242991, 199323991, 199353991, 199363991, 199393991, 199494991, 199515991, 199545991, 199656991, 199767991, 199909991, 199999991]\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        return res[bisect_left(res,n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res=[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821, 1300031, 1303031, 1311131, 1317131, 1327231, 1328231, 1333331, 1335331, 1338331, 1343431, 1360631, 1362631, 1363631, 1371731, 1374731, 1390931, 1407041, 1409041, 1411141, 1412141, 1422241, 1437341, 1444441, 1447441, 1452541, 1456541, 1461641, 1463641, 1464641, 1469641, 1486841, 1489841, 1490941, 1496941, 1508051, 1513151, 1520251, 1532351, 1535351, 1542451, 1548451, 1550551, 1551551, 1556551, 1557551, 1565651, 1572751, 1579751, 1580851, 1583851, 1589851, 1594951, 1597951, 1598951, 1600061, 1609061, 1611161, 1616161, 1628261, 1630361, 1633361, 1640461, 1643461, 1646461, 1654561, 1657561, 1658561, 1660661, 1670761, 1684861, 1685861, 1688861, 1695961, 1703071, 1707071, 1712171, 1714171, 1730371, 1734371, 1737371, 1748471, 1755571, 1761671, 1764671, 1777771, 1793971, 1802081, 1805081, 1820281, 1823281, 1824281, 1826281, 1829281, 1831381, 1832381, 1842481, 1851581, 1853581, 1856581, 1865681, 1876781, 1878781, 1879781, 1880881, 1881881, 1883881, 1884881, 1895981, 1903091, 1908091, 1909091, 1917191, 1924291, 1930391, 1936391, 1941491, 1951591, 1952591, 1957591, 1958591, 1963691, 1968691, 1969691, 1970791, 1976791, 1981891, 1982891, 1984891, 1987891, 1988891, 1993991, 1995991, 1998991, 3001003, 3002003, 3007003, 3016103, 3026203, 3064603, 3065603, 3072703, 3073703, 3075703, 3083803, 3089803, 3091903, 3095903, 3103013, 3106013, 3127213, 3135313, 3140413, 3155513, 3158513, 3160613, 3166613, 3181813, 3187813, 3193913, 3196913, 3198913, 3211123, 3212123, 3218123, 3222223, 3223223, 3228223, 3233323, 3236323, 3241423, 3245423, 3252523, 3256523, 3258523, 3260623, 3267623, 3272723, 3283823, 3285823, 3286823, 3288823, 3291923, 3293923, 3304033, 3305033, 3307033, 3310133, 3315133, 3319133, 3321233, 3329233, 3331333, 3337333, 3343433, 3353533, 3362633, 3364633, 3365633, 3368633, 3380833, 3391933, 3392933, 3400043, 3411143, 3417143, 3424243, 3425243, 3427243, 3439343, 3441443, 3443443, 3444443, 3447443, 3449443, 3452543, 3460643, 3466643, 3470743, 3479743, 3485843, 3487843, 3503053, 3515153, 3517153, 3528253, 3541453, 3553553, 3558553, 3563653, 3569653, 3586853, 3589853, 3590953, 3591953, 3594953, 3601063, 3607063, 3618163, 3621263, 3627263, 3635363, 3643463, 3646463, 3670763, 3673763, 3680863, 3689863, 3698963, 3708073, 3709073, 3716173, 3717173, 3721273, 3722273, 3728273, 3732373, 3743473, 3746473, 3762673, 3763673, 3765673, 3768673, 3769673, 3773773, 3774773, 3781873, 3784873, 3792973, 3793973, 3799973, 3804083, 3806083, 3812183, 3814183, 3826283, 3829283, 3836383, 3842483, 3853583, 3858583, 3863683, 3864683, 3867683, 3869683, 3871783, 3878783, 3893983, 3899983, 3913193, 3916193, 3918193, 3924293, 3927293, 3931393, 3938393, 3942493, 3946493, 3948493, 3964693, 3970793, 3983893, 3991993, 3994993, 3997993, 3998993, 7014107, 7035307, 7036307, 7041407, 7046407, 7057507, 7065607, 7069607, 7073707, 7079707, 7082807, 7084807, 7087807, 7093907, 7096907, 7100017, 7114117, 7115117, 7118117, 7129217, 7134317, 7136317, 7141417, 7145417, 7155517, 7156517, 7158517, 7159517, 7177717, 7190917, 7194917, 7215127, 7226227, 7246427, 7249427, 7250527, 7256527, 7257527, 7261627, 7267627, 7276727, 7278727, 7291927, 7300037, 7302037, 7310137, 7314137, 7324237, 7327237, 7347437, 7352537, 7354537, 7362637, 7365637, 7381837, 7388837, 7392937, 7401047, 7403047, 7409047, 7415147, 7434347, 7436347, 7439347, 7452547, 7461647, 7466647, 7472747, 7475747, 7485847, 7486847, 7489847, 7493947, 7507057, 7508057, 7518157, 7519157, 7521257, 7527257, 7540457, 7562657, 7564657, 7576757, 7586857, 7592957, 7594957, 7600067, 7611167, 7619167, 7622267, 7630367, 7632367, 7644467, 7654567, 7662667, 7665667, 7666667, 7668667, 7669667, 7674767, 7681867, 7690967, 7693967, 7696967, 7715177, 7718177, 7722277, 7729277, 7733377, 7742477, 7747477, 7750577, 7758577, 7764677, 7772777, 7774777, 7778777, 7782877, 7783877, 7791977, 7794977, 7807087, 7819187, 7820287, 7821287, 7831387, 7832387, 7838387, 7843487, 7850587, 7856587, 7865687, 7867687, 7868687, 7873787, 7884887, 7891987, 7897987, 7913197, 7916197, 7930397, 7933397, 7935397, 7938397, 7941497, 7943497, 7949497, 7957597, 7958597, 7960697, 7977797, 7984897, 7985897, 7987897, 7996997, 9002009, 9015109, 9024209, 9037309, 9042409, 9043409, 9045409, 9046409, 9049409, 9067609, 9073709, 9076709, 9078709, 9091909, 9095909, 9103019, 9109019, 9110119, 9127219, 9128219, 9136319, 9149419, 9169619, 9173719, 9174719, 9179719, 9185819, 9196919, 9199919, 9200029, 9209029, 9212129, 9217129, 9222229, 9223229, 9230329, 9231329, 9255529, 9269629, 9271729, 9277729, 9280829, 9286829, 9289829, 9318139, 9320239, 9324239, 9329239, 9332339, 9338339, 9351539, 9357539, 9375739, 9384839, 9397939, 9400049, 9414149, 9419149, 9433349, 9439349, 9440449, 9446449, 9451549, 9470749, 9477749, 9492949, 9493949, 9495949, 9504059, 9514159, 9526259, 9529259, 9547459, 9556559, 9558559, 9561659, 9577759, 9583859, 9585859, 9586859, 9601069, 9602069, 9604069, 9610169, 9620269, 9624269, 9626269, 9632369, 9634369, 9645469, 9650569, 9657569, 9670769, 9686869, 9700079, 9709079, 9711179, 9714179, 9724279, 9727279, 9732379, 9733379, 9743479, 9749479, 9752579, 9754579, 9758579, 9762679, 9770779, 9776779, 9779779, 9781879, 9782879, 9787879, 9788879, 9795979, 9801089, 9807089, 9809089, 9817189, 9818189, 9820289, 9822289, 9836389, 9837389, 9845489, 9852589, 9871789, 9888889, 9889889, 9896989, 9902099, 9907099, 9908099, 9916199, 9918199, 9919199, 9921299, 9923299, 9926299, 9927299, 9931399, 9932399, 9935399, 9938399, 9957599, 9965699, 9978799, 9980899, 9981899, 9989899, 100030001, 100050001, 100060001, 100111001, 100131001, 100161001, 100404001, 100656001, 100707001, 100767001, 100888001, 100999001, 101030101, 101060101, 101141101, 101171101, 101282101, 101292101, 101343101, 101373101, 101414101, 101424101, 101474101, 101595101, 101616101, 101717101, 101777101, 101838101, 101898101, 101919101, 101949101, 101999101, 102040201, 102070201, 102202201, 102232201, 102272201, 102343201, 102383201, 102454201, 102484201, 102515201, 102676201, 102686201, 102707201, 102808201, 102838201, 103000301, 103060301, 103161301, 103212301, 103282301, 103303301, 103323301, 103333301, 103363301, 103464301, 103515301, 103575301, 103696301, 103777301, 103818301, 103828301, 103909301, 103939301, 104000401, 104030401, 104040401, 104111401, 104222401, 104282401, 104333401, 104585401, 104616401, 104787401, 104838401, 104919401, 104949401, 105121501, 105191501, 105202501, 105262501, 105272501, 105313501, 105323501, 105343501, 105575501, 105616501, 105656501, 105757501, 105818501, 105868501, 105929501, 106060601, 106111601, 106131601, 106191601, 106222601, 106272601, 106353601, 106444601, 106464601, 106545601, 106555601, 106717601, 106909601, 106929601, 107000701, 107070701, 107121701, 107232701, 107393701, 107414701, 107424701, 107595701, 107636701, 107646701, 107747701, 107757701, 107828701, 107858701, 107868701, 107888701, 107939701, 107949701, 108070801, 108101801, 108121801, 108151801, 108212801, 108323801, 108373801, 108383801, 108434801, 108464801, 108484801, 108494801, 108505801, 108565801, 108686801, 108707801, 108767801, 108838801, 108919801, 108959801, 109000901, 109101901, 109111901, 109161901, 109333901, 109404901, 109434901, 109444901, 109474901, 109575901, 109656901, 109747901, 109777901, 109797901, 109818901, 109909901, 109929901, 110111011, 110232011, 110252011, 110343011, 110424011, 110505011, 110565011, 110676011, 110747011, 110757011, 110909011, 110949011, 110999011, 111010111, 111020111, 111050111, 111070111, 111181111, 111191111, 111262111, 111272111, 111454111, 111484111, 111515111, 111616111, 111686111, 111757111, 111848111, 112030211, 112060211, 112111211, 112161211, 112171211, 112212211, 112434211, 112494211, 112545211, 112636211, 112878211, 112959211, 112969211, 112989211, 113030311, 113090311, 113111311, 113262311, 113282311, 113474311, 113535311, 113565311, 113616311, 113636311, 113888311, 113939311, 114040411, 114191411, 114232411, 114353411, 114383411, 114484411, 114494411, 114535411, 114727411, 114808411, 114818411, 114848411, 114878411, 114898411, 115000511, 115020511, 115060511, 115111511, 115141511, 115191511, 115212511, 115222511, 115404511, 115464511, 115545511, 115636511, 115737511, 115767511, 115797511, 115828511, 115959511, 116000611, 116010611, 116040611, 116424611, 116505611, 116646611, 116696611, 116757611, 116777611, 116828611, 116868611, 116919611, 117070711, 117101711, 117262711, 117272711, 117323711, 117484711, 117505711, 117515711, 117616711, 117686711, 117757711, 117767711, 117797711, 117818711, 117959711, 118252811, 118272811, 118414811, 118464811, 118525811, 118626811, 118686811, 118696811, 118717811, 118818811, 118848811, 118909811, 118959811, 119010911, 119171911, 119202911, 119343911, 119363911, 119454911, 119585911, 119595911, 119646911, 119676911, 119696911, 119717911, 119787911, 119868911, 119888911, 119969911, 120191021, 120242021, 120434021, 120454021, 120494021, 120535021, 120565021, 120646021, 120808021, 120868021, 120989021, 121080121, 121111121, 121131121, 121161121, 121272121, 121282121, 121393121, 121414121, 121555121, 121747121, 121818121, 121878121, 121939121, 121989121, 122040221, 122232221, 122262221, 122292221, 122333221, 122363221, 122373221, 122393221, 122444221, 122484221, 122535221, 122696221, 122787221, 122858221, 122919221, 123161321, 123292321, 123424321, 123484321, 123494321, 123575321, 123767321, 123838321, 123989321, 124000421, 124080421, 124101421, 124131421, 124252421, 124323421, 124333421, 124434421, 124515421, 124525421, 124626421, 124656421, 124717421, 124737421, 124959421, 124989421, 125000521, 125010521, 125232521, 125252521, 125292521, 125343521, 125474521, 125505521, 125565521, 125606521, 125616521, 125757521, 125838521, 125939521, 125979521, 125999521, 126101621, 126161621, 126181621, 126202621, 126212621, 126323621, 126424621, 126484621, 126535621, 126595621, 126616621, 126676621, 126686621, 126727621, 126737621, 126757621, 126878621, 127060721, 127090721, 127131721, 127212721, 127383721, 127494721, 127545721, 127636721, 127656721, 127686721, 127717721, 127747721, 127828721, 127909721, 127929721, 128070821, 128090821, 128121821, 128181821, 128202821, 128252821, 128262821, 128282821, 128444821, 128474821, 128525821, 128535821, 128595821, 128646821, 128747821, 128787821, 128868821, 128919821, 128939821, 129080921, 129202921, 129292921, 129323921, 129373921, 129484921, 129494921, 129535921, 129737921, 129919921, 129979921, 130020031, 130030031, 130060031, 130141031, 130171031, 130222031, 130333031, 130444031, 130464031, 130545031, 130555031, 130585031, 130606031, 130636031, 130717031, 130767031, 130818031, 130828031, 130858031, 130969031, 131030131, 131111131, 131121131, 131222131, 131252131, 131333131, 131555131, 131565131, 131585131, 131646131, 131676131, 131828131, 132010231, 132191231, 132464231, 132535231, 132595231, 132646231, 132676231, 132757231, 133020331, 133060331, 133111331, 133161331, 133252331, 133474331, 133494331, 133575331, 133686331, 133767331, 133818331, 133909331, 134090431, 134181431, 134232431, 134424431, 134505431, 134525431, 134535431, 134616431, 134757431, 134808431, 134858431, 134888431, 134909431, 134919431, 134979431, 135010531, 135040531, 135101531, 135121531, 135161531, 135262531, 135434531, 135494531, 135515531, 135626531, 135646531, 135707531, 135838531, 135868531, 135878531, 135929531, 135959531, 135979531, 136090631, 136171631, 136222631, 136252631, 136303631, 136363631, 136474631, 136545631, 136737631, 136797631, 136818631, 136909631, 136969631, 137030731, 137040731, 137060731, 137090731, 137151731, 137171731, 137232731, 137282731, 137333731, 137363731, 137424731, 137474731, 137606731, 137636731, 137696731, 137757731, 137808731, 137838731, 137939731, 137999731, 138040831, 138131831, 138242831, 138292831, 138313831, 138383831, 138454831, 138575831, 138616831, 138646831, 138757831, 138898831, 138959831, 138989831, 139131931, 139161931, 139222931, 139252931, 139282931, 139383931, 139474931, 139515931, 139606931, 139626931, 139717931, 139848931, 139959931, 139969931, 139999931, 140000041, 140030041, 140151041, 140303041, 140505041, 140565041, 140606041, 140777041, 140787041, 140828041, 140868041, 140898041, 141020141, 141070141, 141131141, 141151141, 141242141, 141262141, 141313141, 141343141, 141383141, 141484141, 141494141, 141575141, 141595141, 141616141, 141767141, 141787141, 141848141, 142000241, 142030241, 142080241, 142252241, 142272241, 142353241, 142363241, 142464241, 142545241, 142555241, 142686241, 142707241, 142797241, 142858241, 142888241, 143090341, 143181341, 143262341, 143303341, 143454341, 143474341, 143585341, 143636341, 143787341, 143828341, 143919341, 143969341, 144010441, 144020441, 144202441, 144212441, 144313441, 144353441, 144404441, 144434441, 144484441, 144505441, 144707441, 144757441, 144808441, 144818441, 144848441, 144878441, 144898441, 144979441, 144989441, 145020541, 145030541, 145090541, 145353541, 145363541, 145393541, 145464541, 145494541, 145575541, 145666541, 145767541, 146030641, 146040641, 146181641, 146222641, 146252641, 146313641, 146363641, 146505641, 146555641, 146565641, 146676641, 146858641, 146909641, 147191741, 147232741, 147242741, 147313741, 147343741, 147373741, 147434741, 147515741, 147565741, 147616741, 147686741, 147707741, 147757741, 147838741, 147929741, 148020841, 148060841, 148080841, 148414841, 148444841, 148525841, 148545841, 148585841, 148666841, 148686841, 148707841, 148818841, 148858841, 148888841, 148969841, 149000941, 149333941, 149343941, 149484941, 149535941, 149555941, 149616941, 149646941, 149696941, 149858941, 149888941, 149909941, 149919941, 149939941, 150070051, 150151051, 150181051, 150202051, 150272051, 150434051, 150494051, 150505051, 150626051, 150686051, 150727051, 150808051, 150818051, 150979051, 151080151, 151161151, 151212151, 151222151, 151282151, 151353151, 151545151, 151585151, 151656151, 151737151, 151777151, 151858151, 151878151, 151888151, 151959151, 151969151, 151999151, 152090251, 152111251, 152171251, 152181251, 152252251, 152363251, 152393251, 152454251, 152505251, 152565251, 152616251, 152646251, 152666251, 152696251, 152888251, 152939251, 153212351, 153272351, 153292351, 153313351, 153323351, 153404351, 153424351, 153454351, 153484351, 153494351, 153626351, 153808351, 153818351, 153838351, 153979351, 154030451, 154191451, 154252451, 154272451, 154303451, 154323451, 154383451, 154393451, 154474451, 154494451, 154555451, 154575451, 154989451, 155060551, 155141551, 155171551, 155292551, 155313551, 155333551, 155373551, 155424551, 155474551, 155535551, 155646551, 155666551, 155676551, 155808551, 155828551, 155868551, 156151651, 156262651, 156343651, 156424651, 156434651, 156494651, 156545651, 156595651, 156656651, 156707651, 156727651, 156757651, 156848651, 156878651, 156949651, 157090751, 157101751, 157161751, 157252751, 157393751, 157444751, 157555751, 157717751, 157878751, 157888751, 157939751, 157959751, 157989751, 158090851, 158111851, 158222851, 158252851, 158363851, 158474851, 158595851, 158676851, 158696851, 158747851, 158808851, 158858851, 158898851, 158909851, 159020951, 159040951, 159050951, 159121951, 159181951, 159191951, 159202951, 159232951, 159262951, 159292951, 159323951, 159404951, 159464951, 159565951, 159595951, 159646951, 159757951, 159808951, 159919951, 159929951, 159959951, 160020061, 160050061, 160080061, 160101061, 160131061, 160141061, 160161061, 160171061, 160393061, 160545061, 160696061, 160707061, 160717061, 160797061, 160878061, 161171161, 161282161, 161313161, 161363161, 161474161, 161484161, 161535161, 161585161, 161636161, 161787161, 161838161, 161969161, 162040261, 162232261, 162404261, 162464261, 162484261, 162565261, 162686261, 162707261, 162757261, 162898261, 162919261, 162949261, 162959261, 162979261, 162989261, 163101361, 163333361, 163434361, 163464361, 163474361, 163494361, 163515361, 163555361, 163606361, 163686361, 163696361, 163878361, 163959361, 164000461, 164070461, 164151461, 164292461, 164333461, 164454461, 164484461, 164585461, 164616461, 164696461, 164717461, 164727461, 164838461, 165101561, 165161561, 165191561, 165212561, 165343561, 165515561, 165535561, 165808561, 165878561, 165898561, 165919561, 165949561, 166000661, 166080661, 166171661, 166191661, 166404661, 166545661, 166555661, 166636661, 166686661, 166818661, 166828661, 166878661, 166888661, 166929661, 167000761, 167111761, 167262761, 167393761, 167454761, 167474761, 167484761, 167636761, 167646761, 167787761, 167888761, 167898761, 167979761, 168151861, 168191861, 168232861, 168404861, 168505861, 168515861, 168565861, 168818861, 168898861, 168929861, 168949861, 169060961, 169131961, 169141961, 169282961, 169333961, 169383961, 169464961, 169555961, 169606961, 169656961, 169666961, 169686961, 169777961, 169797961, 169858961, 169999961, 170040071, 170060071, 170232071, 170303071, 170333071, 170414071, 170424071, 170484071, 170606071, 170616071, 170646071, 170828071, 170838071, 170909071, 170979071, 171080171, 171262171, 171292171, 171343171, 171565171, 171575171, 171767171, 171919171, 171959171, 172060271, 172090271, 172161271, 172353271, 172363271, 172393271, 172474271, 172585271, 172656271, 172747271, 172767271, 172797271, 172878271, 172909271, 172959271, 173000371, 173030371, 173090371, 173252371, 173373371, 173454371, 173525371, 173585371, 173696371, 173757371, 173777371, 173828371, 173868371, 173888371, 173898371, 173919371, 174080471, 174121471, 174131471, 174181471, 174313471, 174343471, 174595471, 174646471, 174676471, 174919471, 174949471, 174979471, 174989471, 175000571, 175090571, 175101571, 175111571, 175353571, 175444571, 175555571, 175626571, 175747571, 175777571, 175848571, 175909571, 176090671, 176111671, 176141671, 176181671, 176232671, 176313671, 176333671, 176373671, 176393671, 176414671, 176585671, 176636671, 176646671, 176666671, 176696671, 176757671, 176787671, 176888671, 176898671, 176939671, 177121771, 177161771, 177202771, 177242771, 177323771, 177565771, 177616771, 177707771, 177757771, 177868771, 178101871, 178131871, 178141871, 178161871, 178353871, 178414871, 178515871, 178525871, 178656871, 178717871, 178747871, 178878871, 178969871, 178989871, 178999871, 179010971, 179060971, 179222971, 179232971, 179262971, 179414971, 179454971, 179484971, 179717971, 179777971, 179808971, 179858971, 179868971, 179909971, 179969971, 179999971, 180070081, 180101081, 180161081, 180292081, 180515081, 180535081, 180545081, 180565081, 180616081, 180757081, 180959081, 181111181, 181515181, 181545181, 181666181, 181737181, 181797181, 181888181, 182010281, 182202281, 182373281, 182585281, 182616281, 182636281, 182777281, 182858281, 182949281, 183232381, 183626381, 183656381, 183737381, 183898381, 183979381, 183989381, 184030481, 184212481, 184222481, 184303481, 184393481, 184414481, 184545481, 184585481, 184606481, 184636481, 184747481, 184818481, 184878481, 185232581, 185373581, 185393581, 185525581, 185555581, 185595581, 185676581, 185757581, 185838581, 185858581, 185868581, 185999581, 186010681, 186040681, 186050681, 186070681, 186101681, 186131681, 186151681, 186161681, 186424681, 186484681, 186505681, 186565681, 186656681, 186676681, 186787681, 186898681, 187090781, 187101781, 187111781, 187161781, 187272781, 187404781, 187434781, 187444781, 187525781, 187767781, 187909781, 187939781, 187999781, 188010881, 188060881, 188141881, 188151881, 188303881, 188373881, 188414881, 188454881, 188505881, 188525881, 188535881, 188616881, 188636881, 188646881, 188727881, 188777881, 188868881, 188888881, 188898881, 188979881, 189080981, 189131981, 189262981, 189292981, 189464981, 189535981, 189595981, 189727981, 189787981, 189838981, 189898981, 189929981, 190000091, 190020091, 190080091, 190101091, 190252091, 190404091, 190434091, 190464091, 190494091, 190656091, 190696091, 190717091, 190747091, 190777091, 190858091, 190909091, 191090191, 191171191, 191232191, 191292191, 191313191, 191565191, 191595191, 191727191, 191757191, 191838191, 191868191, 191939191, 191969191, 192101291, 192191291, 192202291, 192242291, 192313291, 192404291, 192454291, 192484291, 192767291, 192797291, 192898291, 193000391, 193030391, 193191391, 193212391, 193282391, 193303391, 193383391, 193414391, 193464391, 193555391, 193686391, 193858391, 193888391, 194000491, 194070491, 194121491, 194222491, 194232491, 194292491, 194303491, 194393491, 194505491, 194595491, 194606491, 194787491, 194939491, 194999491, 195010591, 195040591, 195070591, 195151591, 195202591, 195242591, 195353591, 195505591, 195545591, 195707591, 195767591, 195868591, 195878591, 195949591, 195979591, 196000691, 196090691, 196323691, 196333691, 196363691, 196696691, 196797691, 196828691, 196878691, 197030791, 197060791, 197070791, 197090791, 197111791, 197121791, 197202791, 197292791, 197343791, 197454791, 197525791, 197606791, 197616791, 197868791, 197898791, 197919791, 198040891, 198070891, 198080891, 198131891, 198292891, 198343891, 198353891, 198383891, 198454891, 198565891, 198656891, 198707891, 198787891, 198878891, 198919891, 199030991, 199080991, 199141991, 199171991, 199212991, 199242991, 199323991, 199353991, 199363991, 199393991, 199494991, 199515991, 199545991, 199656991, 199767991, 199909991, 199999991]\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        return res[bisect_left(res,n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, N: int) -> int:\n",
    "        \n",
    "        list_sushu = [2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821, 1300031, 1303031, 1311131, 1317131, 1327231, 1328231, 1333331, 1335331, 1338331, 1343431, 1360631, 1362631, 1363631, 1371731, 1374731, 1390931, 1407041, 1409041, 1411141, 1412141, 1422241, 1437341, 1444441, 1447441, 1452541, 1456541, 1461641, 1463641, 1464641, 1469641, 1486841, 1489841, 1490941, 1496941, 1508051, 1513151, 1520251, 1532351, 1535351, 1542451, 1548451, 1550551, 1551551, 1556551, 1557551, 1565651, 1572751, 1579751, 1580851, 1583851, 1589851, 1594951, 1597951, 1598951, 1600061, 1609061, 1611161, 1616161, 1628261, 1630361, 1633361, 1640461, 1643461, 1646461, 1654561, 1657561, 1658561, 1660661, 1670761, 1684861, 1685861, 1688861, 1695961, 1703071, 1707071, 1712171, 1714171, 1730371, 1734371, 1737371, 1748471, 1755571, 1761671, 1764671, 1777771, 1793971, 1802081, 1805081, 1820281, 1823281, 1824281, 1826281, 1829281, 1831381, 1832381, 1842481, 1851581, 1853581, 1856581, 1865681, 1876781, 1878781, 1879781, 1880881, 1881881, 1883881, 1884881, 1895981, 1903091, 1908091, 1909091, 1917191, 1924291, 1930391, 1936391, 1941491, 1951591, 1952591, 1957591, 1958591, 1963691, 1968691, 1969691, 1970791, 1976791, 1981891, 1982891, 1984891, 1987891, 1988891, 1993991, 1995991, 1998991, 3001003, 3002003, 3007003, 3016103, 3026203, 3064603, 3065603, 3072703, 3073703, 3075703, 3083803, 3089803, 3091903, 3095903, 3103013, 3106013, 3127213, 3135313, 3140413, 3155513, 3158513, 3160613, 3166613, 3181813, 3187813, 3193913, 3196913, 3198913, 3211123, 3212123, 3218123, 3222223, 3223223, 3228223, 3233323, 3236323, 3241423, 3245423, 3252523, 3256523, 3258523, 3260623, 3267623, 3272723, 3283823, 3285823, 3286823, 3288823, 3291923, 3293923, 3304033, 3305033, 3307033, 3310133, 3315133, 3319133, 3321233, 3329233, 3331333, 3337333, 3343433, 3353533, 3362633, 3364633, 3365633, 3368633, 3380833, 3391933, 3392933, 3400043, 3411143, 3417143, 3424243, 3425243, 3427243, 3439343, 3441443, 3443443, 3444443, 3447443, 3449443, 3452543, 3460643, 3466643, 3470743, 3479743, 3485843, 3487843, 3503053, 3515153, 3517153, 3528253, 3541453, 3553553, 3558553, 3563653, 3569653, 3586853, 3589853, 3590953, 3591953, 3594953, 3601063, 3607063, 3618163, 3621263, 3627263, 3635363, 3643463, 3646463, 3670763, 3673763, 3680863, 3689863, 3698963, 3708073, 3709073, 3716173, 3717173, 3721273, 3722273, 3728273, 3732373, 3743473, 3746473, 3762673, 3763673, 3765673, 3768673, 3769673, 3773773, 3774773, 3781873, 3784873, 3792973, 3793973, 3799973, 3804083, 3806083, 3812183, 3814183, 3826283, 3829283, 3836383, 3842483, 3853583, 3858583, 3863683, 3864683, 3867683, 3869683, 3871783, 3878783, 3893983, 3899983, 3913193, 3916193, 3918193, 3924293, 3927293, 3931393, 3938393, 3942493, 3946493, 3948493, 3964693, 3970793, 3983893, 3991993, 3994993, 3997993, 3998993, 7014107, 7035307, 7036307, 7041407, 7046407, 7057507, 7065607, 7069607, 7073707, 7079707, 7082807, 7084807, 7087807, 7093907, 7096907, 7100017, 7114117, 7115117, 7118117, 7129217, 7134317, 7136317, 7141417, 7145417, 7155517, 7156517, 7158517, 7159517, 7177717, 7190917, 7194917, 7215127, 7226227, 7246427, 7249427, 7250527, 7256527, 7257527, 7261627, 7267627, 7276727, 7278727, 7291927, 7300037, 7302037, 7310137, 7314137, 7324237, 7327237, 7347437, 7352537, 7354537, 7362637, 7365637, 7381837, 7388837, 7392937, 7401047, 7403047, 7409047, 7415147, 7434347, 7436347, 7439347, 7452547, 7461647, 7466647, 7472747, 7475747, 7485847, 7486847, 7489847, 7493947, 7507057, 7508057, 7518157, 7519157, 7521257, 7527257, 7540457, 7562657, 7564657, 7576757, 7586857, 7592957, 7594957, 7600067, 7611167, 7619167, 7622267, 7630367, 7632367, 7644467, 7654567, 7662667, 7665667, 7666667, 7668667, 7669667, 7674767, 7681867, 7690967, 7693967, 7696967, 7715177, 7718177, 7722277, 7729277, 7733377, 7742477, 7747477, 7750577, 7758577, 7764677, 7772777, 7774777, 7778777, 7782877, 7783877, 7791977, 7794977, 7807087, 7819187, 7820287, 7821287, 7831387, 7832387, 7838387, 7843487, 7850587, 7856587, 7865687, 7867687, 7868687, 7873787, 7884887, 7891987, 7897987, 7913197, 7916197, 7930397, 7933397, 7935397, 7938397, 7941497, 7943497, 7949497, 7957597, 7958597, 7960697, 7977797, 7984897, 7985897, 7987897, 7996997, 9002009, 9015109, 9024209, 9037309, 9042409, 9043409, 9045409, 9046409, 9049409, 9067609, 9073709, 9076709, 9078709, 9091909, 9095909, 9103019, 9109019, 9110119, 9127219, 9128219, 9136319, 9149419, 9169619, 9173719, 9174719, 9179719, 9185819, 9196919, 9199919, 9200029, 9209029, 9212129, 9217129, 9222229, 9223229, 9230329, 9231329, 9255529, 9269629, 9271729, 9277729, 9280829, 9286829, 9289829, 9318139, 9320239, 9324239, 9329239, 9332339, 9338339, 9351539, 9357539, 9375739, 9384839, 9397939, 9400049, 9414149, 9419149, 9433349, 9439349, 9440449, 9446449, 9451549, 9470749, 9477749, 9492949, 9493949, 9495949, 9504059, 9514159, 9526259, 9529259, 9547459, 9556559, 9558559, 9561659, 9577759, 9583859, 9585859, 9586859, 9601069, 9602069, 9604069, 9610169, 9620269, 9624269, 9626269, 9632369, 9634369, 9645469, 9650569, 9657569, 9670769, 9686869, 9700079, 9709079, 9711179, 9714179, 9724279, 9727279, 9732379, 9733379, 9743479, 9749479, 9752579, 9754579, 9758579, 9762679, 9770779, 9776779, 9779779, 9781879, 9782879, 9787879, 9788879, 9795979, 9801089, 9807089, 9809089, 9817189, 9818189, 9820289, 9822289, 9836389, 9837389, 9845489, 9852589, 9871789, 9888889, 9889889, 9896989, 9902099, 9907099, 9908099, 9916199, 9918199, 9919199, 9921299, 9923299, 9926299, 9927299, 9931399, 9932399, 9935399, 9938399, 9957599, 9965699, 9978799, 9980899, 9981899, 9989899, 100030001, 100050001, 100060001, 100111001, 100131001, 100161001, 100404001, 100656001, 100707001, 100767001, 100888001, 100999001, 101030101, 101060101, 101141101, 101171101, 101282101, 101292101, 101343101, 101373101, 101414101, 101424101, 101474101, 101595101, 101616101, 101717101, 101777101, 101838101, 101898101, 101919101, 101949101, 101999101, 102040201, 102070201, 102202201, 102232201, 102272201, 102343201, 102383201, 102454201, 102484201, 102515201, 102676201, 102686201, 102707201, 102808201, 102838201, 103000301, 103060301, 103161301, 103212301, 103282301, 103303301, 103323301, 103333301, 103363301, 103464301, 103515301, 103575301, 103696301, 103777301, 103818301, 103828301, 103909301, 103939301, 104000401, 104030401, 104040401, 104111401, 104222401, 104282401, 104333401, 104585401, 104616401, 104787401, 104838401, 104919401, 104949401, 105121501, 105191501, 105202501, 105262501, 105272501, 105313501, 105323501, 105343501, 105575501, 105616501, 105656501, 105757501, 105818501, 105868501, 105929501, 106060601, 106111601, 106131601, 106191601, 106222601, 106272601, 106353601, 106444601, 106464601, 106545601, 106555601, 106717601, 106909601, 106929601, 107000701, 107070701, 107121701, 107232701, 107393701, 107414701, 107424701, 107595701, 107636701, 107646701, 107747701, 107757701, 107828701, 107858701, 107868701, 107888701, 107939701, 107949701, 108070801, 108101801, 108121801, 108151801, 108212801, 108323801, 108373801, 108383801, 108434801, 108464801, 108484801, 108494801, 108505801, 108565801, 108686801, 108707801, 108767801, 108838801, 108919801, 108959801, 109000901, 109101901, 109111901, 109161901, 109333901, 109404901, 109434901, 109444901, 109474901, 109575901, 109656901, 109747901, 109777901, 109797901, 109818901, 109909901, 109929901, 110111011, 110232011, 110252011, 110343011, 110424011, 110505011, 110565011, 110676011, 110747011, 110757011, 110909011, 110949011, 110999011, 111010111, 111020111, 111050111, 111070111, 111181111, 111191111, 111262111, 111272111, 111454111, 111484111, 111515111, 111616111, 111686111, 111757111, 111848111, 112030211, 112060211, 112111211, 112161211, 112171211, 112212211, 112434211, 112494211, 112545211, 112636211, 112878211, 112959211, 112969211, 112989211, 113030311, 113090311, 113111311, 113262311, 113282311, 113474311, 113535311, 113565311, 113616311, 113636311, 113888311, 113939311, 114040411, 114191411, 114232411, 114353411, 114383411, 114484411, 114494411, 114535411, 114727411, 114808411, 114818411, 114848411, 114878411, 114898411, 115000511, 115020511, 115060511, 115111511, 115141511, 115191511, 115212511, 115222511, 115404511, 115464511, 115545511, 115636511, 115737511, 115767511, 115797511, 115828511, 115959511, 116000611, 116010611, 116040611, 116424611, 116505611, 116646611, 116696611, 116757611, 116777611, 116828611, 116868611, 116919611, 117070711, 117101711, 117262711, 117272711, 117323711, 117484711, 117505711, 117515711, 117616711, 117686711, 117757711, 117767711, 117797711, 117818711, 117959711, 118252811, 118272811, 118414811, 118464811, 118525811, 118626811, 118686811, 118696811, 118717811, 118818811, 118848811, 118909811, 118959811, 119010911, 119171911, 119202911, 119343911, 119363911, 119454911, 119585911, 119595911, 119646911, 119676911, 119696911, 119717911, 119787911, 119868911, 119888911, 119969911, 120191021, 120242021, 120434021, 120454021, 120494021, 120535021, 120565021, 120646021, 120808021, 120868021, 120989021, 121080121, 121111121, 121131121, 121161121, 121272121, 121282121, 121393121, 121414121, 121555121, 121747121, 121818121, 121878121, 121939121, 121989121, 122040221, 122232221, 122262221, 122292221, 122333221, 122363221, 122373221, 122393221, 122444221, 122484221, 122535221, 122696221, 122787221, 122858221, 122919221, 123161321, 123292321, 123424321, 123484321, 123494321, 123575321, 123767321, 123838321, 123989321, 124000421, 124080421, 124101421, 124131421, 124252421, 124323421, 124333421, 124434421, 124515421, 124525421, 124626421, 124656421, 124717421, 124737421, 124959421, 124989421, 125000521, 125010521, 125232521, 125252521, 125292521, 125343521, 125474521, 125505521, 125565521, 125606521, 125616521, 125757521, 125838521, 125939521, 125979521, 125999521, 126101621, 126161621, 126181621, 126202621, 126212621, 126323621, 126424621, 126484621, 126535621, 126595621, 126616621, 126676621, 126686621, 126727621, 126737621, 126757621, 126878621, 127060721, 127090721, 127131721, 127212721, 127383721, 127494721, 127545721, 127636721, 127656721, 127686721, 127717721, 127747721, 127828721, 127909721, 127929721, 128070821, 128090821, 128121821, 128181821, 128202821, 128252821, 128262821, 128282821, 128444821, 128474821, 128525821, 128535821, 128595821, 128646821, 128747821, 128787821, 128868821, 128919821, 128939821, 129080921, 129202921, 129292921, 129323921, 129373921, 129484921, 129494921, 129535921, 129737921, 129919921, 129979921, 130020031, 130030031, 130060031, 130141031, 130171031, 130222031, 130333031, 130444031, 130464031, 130545031, 130555031, 130585031, 130606031, 130636031, 130717031, 130767031, 130818031, 130828031, 130858031, 130969031, 131030131, 131111131, 131121131, 131222131, 131252131, 131333131, 131555131, 131565131, 131585131, 131646131, 131676131, 131828131, 132010231, 132191231, 132464231, 132535231, 132595231, 132646231, 132676231, 132757231, 133020331, 133060331, 133111331, 133161331, 133252331, 133474331, 133494331, 133575331, 133686331, 133767331, 133818331, 133909331, 134090431, 134181431, 134232431, 134424431, 134505431, 134525431, 134535431, 134616431, 134757431, 134808431, 134858431, 134888431, 134909431, 134919431, 134979431, 135010531, 135040531, 135101531, 135121531, 135161531, 135262531, 135434531, 135494531, 135515531, 135626531, 135646531, 135707531, 135838531, 135868531, 135878531, 135929531, 135959531, 135979531, 136090631, 136171631, 136222631, 136252631, 136303631, 136363631, 136474631, 136545631, 136737631, 136797631, 136818631, 136909631, 136969631, 137030731, 137040731, 137060731, 137090731, 137151731, 137171731, 137232731, 137282731, 137333731, 137363731, 137424731, 137474731, 137606731, 137636731, 137696731, 137757731, 137808731, 137838731, 137939731, 137999731, 138040831, 138131831, 138242831, 138292831, 138313831, 138383831, 138454831, 138575831, 138616831, 138646831, 138757831, 138898831, 138959831, 138989831, 139131931, 139161931, 139222931, 139252931, 139282931, 139383931, 139474931, 139515931, 139606931, 139626931, 139717931, 139848931, 139959931, 139969931, 139999931, 140000041, 140030041, 140151041, 140303041, 140505041, 140565041, 140606041, 140777041, 140787041, 140828041, 140868041, 140898041, 141020141, 141070141, 141131141, 141151141, 141242141, 141262141, 141313141, 141343141, 141383141, 141484141, 141494141, 141575141, 141595141, 141616141, 141767141, 141787141, 141848141, 142000241, 142030241, 142080241, 142252241, 142272241, 142353241, 142363241, 142464241, 142545241, 142555241, 142686241, 142707241, 142797241, 142858241, 142888241, 143090341, 143181341, 143262341, 143303341, 143454341, 143474341, 143585341, 143636341, 143787341, 143828341, 143919341, 143969341, 144010441, 144020441, 144202441, 144212441, 144313441, 144353441, 144404441, 144434441, 144484441, 144505441, 144707441, 144757441, 144808441, 144818441, 144848441, 144878441, 144898441, 144979441, 144989441, 145020541, 145030541, 145090541, 145353541, 145363541, 145393541, 145464541, 145494541, 145575541, 145666541, 145767541, 146030641, 146040641, 146181641, 146222641, 146252641, 146313641, 146363641, 146505641, 146555641, 146565641, 146676641, 146858641, 146909641, 147191741, 147232741, 147242741, 147313741, 147343741, 147373741, 147434741, 147515741, 147565741, 147616741, 147686741, 147707741, 147757741, 147838741, 147929741, 148020841, 148060841, 148080841, 148414841, 148444841, 148525841, 148545841, 148585841, 148666841, 148686841, 148707841, 148818841, 148858841, 148888841, 148969841, 149000941, 149333941, 149343941, 149484941, 149535941, 149555941, 149616941, 149646941, 149696941, 149858941, 149888941, 149909941, 149919941, 149939941, 150070051, 150151051, 150181051, 150202051, 150272051, 150434051, 150494051, 150505051, 150626051, 150686051, 150727051, 150808051, 150818051, 150979051, 151080151, 151161151, 151212151, 151222151, 151282151, 151353151, 151545151, 151585151, 151656151, 151737151, 151777151, 151858151, 151878151, 151888151, 151959151, 151969151, 151999151, 152090251, 152111251, 152171251, 152181251, 152252251, 152363251, 152393251, 152454251, 152505251, 152565251, 152616251, 152646251, 152666251, 152696251, 152888251, 152939251, 153212351, 153272351, 153292351, 153313351, 153323351, 153404351, 153424351, 153454351, 153484351, 153494351, 153626351, 153808351, 153818351, 153838351, 153979351, 154030451, 154191451, 154252451, 154272451, 154303451, 154323451, 154383451, 154393451, 154474451, 154494451, 154555451, 154575451, 154989451, 155060551, 155141551, 155171551, 155292551, 155313551, 155333551, 155373551, 155424551, 155474551, 155535551, 155646551, 155666551, 155676551, 155808551, 155828551, 155868551, 156151651, 156262651, 156343651, 156424651, 156434651, 156494651, 156545651, 156595651, 156656651, 156707651, 156727651, 156757651, 156848651, 156878651, 156949651, 157090751, 157101751, 157161751, 157252751, 157393751, 157444751, 157555751, 157717751, 157878751, 157888751, 157939751, 157959751, 157989751, 158090851, 158111851, 158222851, 158252851, 158363851, 158474851, 158595851, 158676851, 158696851, 158747851, 158808851, 158858851, 158898851, 158909851, 159020951, 159040951, 159050951, 159121951, 159181951, 159191951, 159202951, 159232951, 159262951, 159292951, 159323951, 159404951, 159464951, 159565951, 159595951, 159646951, 159757951, 159808951, 159919951, 159929951, 159959951, 160020061, 160050061, 160080061, 160101061, 160131061, 160141061, 160161061, 160171061, 160393061, 160545061, 160696061, 160707061, 160717061, 160797061, 160878061, 161171161, 161282161, 161313161, 161363161, 161474161, 161484161, 161535161, 161585161, 161636161, 161787161, 161838161, 161969161, 162040261, 162232261, 162404261, 162464261, 162484261, 162565261, 162686261, 162707261, 162757261, 162898261, 162919261, 162949261, 162959261, 162979261, 162989261, 163101361, 163333361, 163434361, 163464361, 163474361, 163494361, 163515361, 163555361, 163606361, 163686361, 163696361, 163878361, 163959361, 164000461, 164070461, 164151461, 164292461, 164333461, 164454461, 164484461, 164585461, 164616461, 164696461, 164717461, 164727461, 164838461, 165101561, 165161561, 165191561, 165212561, 165343561, 165515561, 165535561, 165808561, 165878561, 165898561, 165919561, 165949561, 166000661, 166080661, 166171661, 166191661, 166404661, 166545661, 166555661, 166636661, 166686661, 166818661, 166828661, 166878661, 166888661, 166929661, 167000761, 167111761, 167262761, 167393761, 167454761, 167474761, 167484761, 167636761, 167646761, 167787761, 167888761, 167898761, 167979761, 168151861, 168191861, 168232861, 168404861, 168505861, 168515861, 168565861, 168818861, 168898861, 168929861, 168949861, 169060961, 169131961, 169141961, 169282961, 169333961, 169383961, 169464961, 169555961, 169606961, 169656961, 169666961, 169686961, 169777961, 169797961, 169858961, 169999961, 170040071, 170060071, 170232071, 170303071, 170333071, 170414071, 170424071, 170484071, 170606071, 170616071, 170646071, 170828071, 170838071, 170909071, 170979071, 171080171, 171262171, 171292171, 171343171, 171565171, 171575171, 171767171, 171919171, 171959171, 172060271, 172090271, 172161271, 172353271, 172363271, 172393271, 172474271, 172585271, 172656271, 172747271, 172767271, 172797271, 172878271, 172909271, 172959271, 173000371, 173030371, 173090371, 173252371, 173373371, 173454371, 173525371, 173585371, 173696371, 173757371, 173777371, 173828371, 173868371, 173888371, 173898371, 173919371, 174080471, 174121471, 174131471, 174181471, 174313471, 174343471, 174595471, 174646471, 174676471, 174919471, 174949471, 174979471, 174989471, 175000571, 175090571, 175101571, 175111571, 175353571, 175444571, 175555571, 175626571, 175747571, 175777571, 175848571, 175909571, 176090671, 176111671, 176141671, 176181671, 176232671, 176313671, 176333671, 176373671, 176393671, 176414671, 176585671, 176636671, 176646671, 176666671, 176696671, 176757671, 176787671, 176888671, 176898671, 176939671, 177121771, 177161771, 177202771, 177242771, 177323771, 177565771, 177616771, 177707771, 177757771, 177868771, 178101871, 178131871, 178141871, 178161871, 178353871, 178414871, 178515871, 178525871, 178656871, 178717871, 178747871, 178878871, 178969871, 178989871, 178999871, 179010971, 179060971, 179222971, 179232971, 179262971, 179414971, 179454971, 179484971, 179717971, 179777971, 179808971, 179858971, 179868971, 179909971, 179969971, 179999971, 180070081, 180101081, 180161081, 180292081, 180515081, 180535081, 180545081, 180565081, 180616081, 180757081, 180959081, 181111181, 181515181, 181545181, 181666181, 181737181, 181797181, 181888181, 182010281, 182202281, 182373281, 182585281, 182616281, 182636281, 182777281, 182858281, 182949281, 183232381, 183626381, 183656381, 183737381, 183898381, 183979381, 183989381, 184030481, 184212481, 184222481, 184303481, 184393481, 184414481, 184545481, 184585481, 184606481, 184636481, 184747481, 184818481, 184878481, 185232581, 185373581, 185393581, 185525581, 185555581, 185595581, 185676581, 185757581, 185838581, 185858581, 185868581, 185999581, 186010681, 186040681, 186050681, 186070681, 186101681, 186131681, 186151681, 186161681, 186424681, 186484681, 186505681, 186565681, 186656681, 186676681, 186787681, 186898681, 187090781, 187101781, 187111781, 187161781, 187272781, 187404781, 187434781, 187444781, 187525781, 187767781, 187909781, 187939781, 187999781, 188010881, 188060881, 188141881, 188151881, 188303881, 188373881, 188414881, 188454881, 188505881, 188525881, 188535881, 188616881, 188636881, 188646881, 188727881, 188777881, 188868881, 188888881, 188898881, 188979881, 189080981, 189131981, 189262981, 189292981, 189464981, 189535981, 189595981, 189727981, 189787981, 189838981, 189898981, 189929981, 190000091, 190020091, 190080091, 190101091, 190252091, 190404091, 190434091, 190464091, 190494091, 190656091, 190696091, 190717091, 190747091, 190777091, 190858091, 190909091, 191090191, 191171191, 191232191, 191292191, 191313191, 191565191, 191595191, 191727191, 191757191, 191838191, 191868191, 191939191, 191969191, 192101291, 192191291, 192202291, 192242291, 192313291, 192404291, 192454291, 192484291, 192767291, 192797291, 192898291, 193000391, 193030391, 193191391, 193212391, 193282391, 193303391, 193383391, 193414391, 193464391, 193555391, 193686391, 193858391, 193888391, 194000491, 194070491, 194121491, 194222491, 194232491, 194292491, 194303491, 194393491, 194505491, 194595491, 194606491, 194787491, 194939491, 194999491, 195010591, 195040591, 195070591, 195151591, 195202591, 195242591, 195353591, 195505591, 195545591, 195707591, 195767591, 195868591, 195878591, 195949591, 195979591, 196000691, 196090691, 196323691, 196333691, 196363691, 196696691, 196797691, 196828691, 196878691, 197030791, 197060791, 197070791, 197090791, 197111791, 197121791, 197202791, 197292791, 197343791, 197454791, 197525791, 197606791, 197616791, 197868791, 197898791, 197919791, 198040891, 198070891, 198080891, 198131891, 198292891, 198343891, 198353891, 198383891, 198454891, 198565891, 198656891, 198707891, 198787891, 198878891, 198919891, 199030991, 199080991, 199141991, 199171991, 199212991, 199242991, 199323991, 199353991, 199363991, 199393991, 199494991, 199515991, 199545991, 199656991, 199767991, 199909991, 199999991]\n",
    "\n",
    "        for i in range(len(list_sushu)):\n",
    "            if int(list_sushu[i]) >=N:\n",
    "                return list_sushu[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res=[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821, 1300031, 1303031, 1311131, 1317131, 1327231, 1328231, 1333331, 1335331, 1338331, 1343431, 1360631, 1362631, 1363631, 1371731, 1374731, 1390931, 1407041, 1409041, 1411141, 1412141, 1422241, 1437341, 1444441, 1447441, 1452541, 1456541, 1461641, 1463641, 1464641, 1469641, 1486841, 1489841, 1490941, 1496941, 1508051, 1513151, 1520251, 1532351, 1535351, 1542451, 1548451, 1550551, 1551551, 1556551, 1557551, 1565651, 1572751, 1579751, 1580851, 1583851, 1589851, 1594951, 1597951, 1598951, 1600061, 1609061, 1611161, 1616161, 1628261, 1630361, 1633361, 1640461, 1643461, 1646461, 1654561, 1657561, 1658561, 1660661, 1670761, 1684861, 1685861, 1688861, 1695961, 1703071, 1707071, 1712171, 1714171, 1730371, 1734371, 1737371, 1748471, 1755571, 1761671, 1764671, 1777771, 1793971, 1802081, 1805081, 1820281, 1823281, 1824281, 1826281, 1829281, 1831381, 1832381, 1842481, 1851581, 1853581, 1856581, 1865681, 1876781, 1878781, 1879781, 1880881, 1881881, 1883881, 1884881, 1895981, 1903091, 1908091, 1909091, 1917191, 1924291, 1930391, 1936391, 1941491, 1951591, 1952591, 1957591, 1958591, 1963691, 1968691, 1969691, 1970791, 1976791, 1981891, 1982891, 1984891, 1987891, 1988891, 1993991, 1995991, 1998991, 3001003, 3002003, 3007003, 3016103, 3026203, 3064603, 3065603, 3072703, 3073703, 3075703, 3083803, 3089803, 3091903, 3095903, 3103013, 3106013, 3127213, 3135313, 3140413, 3155513, 3158513, 3160613, 3166613, 3181813, 3187813, 3193913, 3196913, 3198913, 3211123, 3212123, 3218123, 3222223, 3223223, 3228223, 3233323, 3236323, 3241423, 3245423, 3252523, 3256523, 3258523, 3260623, 3267623, 3272723, 3283823, 3285823, 3286823, 3288823, 3291923, 3293923, 3304033, 3305033, 3307033, 3310133, 3315133, 3319133, 3321233, 3329233, 3331333, 3337333, 3343433, 3353533, 3362633, 3364633, 3365633, 3368633, 3380833, 3391933, 3392933, 3400043, 3411143, 3417143, 3424243, 3425243, 3427243, 3439343, 3441443, 3443443, 3444443, 3447443, 3449443, 3452543, 3460643, 3466643, 3470743, 3479743, 3485843, 3487843, 3503053, 3515153, 3517153, 3528253, 3541453, 3553553, 3558553, 3563653, 3569653, 3586853, 3589853, 3590953, 3591953, 3594953, 3601063, 3607063, 3618163, 3621263, 3627263, 3635363, 3643463, 3646463, 3670763, 3673763, 3680863, 3689863, 3698963, 3708073, 3709073, 3716173, 3717173, 3721273, 3722273, 3728273, 3732373, 3743473, 3746473, 3762673, 3763673, 3765673, 3768673, 3769673, 3773773, 3774773, 3781873, 3784873, 3792973, 3793973, 3799973, 3804083, 3806083, 3812183, 3814183, 3826283, 3829283, 3836383, 3842483, 3853583, 3858583, 3863683, 3864683, 3867683, 3869683, 3871783, 3878783, 3893983, 3899983, 3913193, 3916193, 3918193, 3924293, 3927293, 3931393, 3938393, 3942493, 3946493, 3948493, 3964693, 3970793, 3983893, 3991993, 3994993, 3997993, 3998993, 7014107, 7035307, 7036307, 7041407, 7046407, 7057507, 7065607, 7069607, 7073707, 7079707, 7082807, 7084807, 7087807, 7093907, 7096907, 7100017, 7114117, 7115117, 7118117, 7129217, 7134317, 7136317, 7141417, 7145417, 7155517, 7156517, 7158517, 7159517, 7177717, 7190917, 7194917, 7215127, 7226227, 7246427, 7249427, 7250527, 7256527, 7257527, 7261627, 7267627, 7276727, 7278727, 7291927, 7300037, 7302037, 7310137, 7314137, 7324237, 7327237, 7347437, 7352537, 7354537, 7362637, 7365637, 7381837, 7388837, 7392937, 7401047, 7403047, 7409047, 7415147, 7434347, 7436347, 7439347, 7452547, 7461647, 7466647, 7472747, 7475747, 7485847, 7486847, 7489847, 7493947, 7507057, 7508057, 7518157, 7519157, 7521257, 7527257, 7540457, 7562657, 7564657, 7576757, 7586857, 7592957, 7594957, 7600067, 7611167, 7619167, 7622267, 7630367, 7632367, 7644467, 7654567, 7662667, 7665667, 7666667, 7668667, 7669667, 7674767, 7681867, 7690967, 7693967, 7696967, 7715177, 7718177, 7722277, 7729277, 7733377, 7742477, 7747477, 7750577, 7758577, 7764677, 7772777, 7774777, 7778777, 7782877, 7783877, 7791977, 7794977, 7807087, 7819187, 7820287, 7821287, 7831387, 7832387, 7838387, 7843487, 7850587, 7856587, 7865687, 7867687, 7868687, 7873787, 7884887, 7891987, 7897987, 7913197, 7916197, 7930397, 7933397, 7935397, 7938397, 7941497, 7943497, 7949497, 7957597, 7958597, 7960697, 7977797, 7984897, 7985897, 7987897, 7996997, 9002009, 9015109, 9024209, 9037309, 9042409, 9043409, 9045409, 9046409, 9049409, 9067609, 9073709, 9076709, 9078709, 9091909, 9095909, 9103019, 9109019, 9110119, 9127219, 9128219, 9136319, 9149419, 9169619, 9173719, 9174719, 9179719, 9185819, 9196919, 9199919, 9200029, 9209029, 9212129, 9217129, 9222229, 9223229, 9230329, 9231329, 9255529, 9269629, 9271729, 9277729, 9280829, 9286829, 9289829, 9318139, 9320239, 9324239, 9329239, 9332339, 9338339, 9351539, 9357539, 9375739, 9384839, 9397939, 9400049, 9414149, 9419149, 9433349, 9439349, 9440449, 9446449, 9451549, 9470749, 9477749, 9492949, 9493949, 9495949, 9504059, 9514159, 9526259, 9529259, 9547459, 9556559, 9558559, 9561659, 9577759, 9583859, 9585859, 9586859, 9601069, 9602069, 9604069, 9610169, 9620269, 9624269, 9626269, 9632369, 9634369, 9645469, 9650569, 9657569, 9670769, 9686869, 9700079, 9709079, 9711179, 9714179, 9724279, 9727279, 9732379, 9733379, 9743479, 9749479, 9752579, 9754579, 9758579, 9762679, 9770779, 9776779, 9779779, 9781879, 9782879, 9787879, 9788879, 9795979, 9801089, 9807089, 9809089, 9817189, 9818189, 9820289, 9822289, 9836389, 9837389, 9845489, 9852589, 9871789, 9888889, 9889889, 9896989, 9902099, 9907099, 9908099, 9916199, 9918199, 9919199, 9921299, 9923299, 9926299, 9927299, 9931399, 9932399, 9935399, 9938399, 9957599, 9965699, 9978799, 9980899, 9981899, 9989899, 100030001, 100050001, 100060001, 100111001, 100131001, 100161001, 100404001, 100656001, 100707001, 100767001, 100888001, 100999001, 101030101, 101060101, 101141101, 101171101, 101282101, 101292101, 101343101, 101373101, 101414101, 101424101, 101474101, 101595101, 101616101, 101717101, 101777101, 101838101, 101898101, 101919101, 101949101, 101999101, 102040201, 102070201, 102202201, 102232201, 102272201, 102343201, 102383201, 102454201, 102484201, 102515201, 102676201, 102686201, 102707201, 102808201, 102838201, 103000301, 103060301, 103161301, 103212301, 103282301, 103303301, 103323301, 103333301, 103363301, 103464301, 103515301, 103575301, 103696301, 103777301, 103818301, 103828301, 103909301, 103939301, 104000401, 104030401, 104040401, 104111401, 104222401, 104282401, 104333401, 104585401, 104616401, 104787401, 104838401, 104919401, 104949401, 105121501, 105191501, 105202501, 105262501, 105272501, 105313501, 105323501, 105343501, 105575501, 105616501, 105656501, 105757501, 105818501, 105868501, 105929501, 106060601, 106111601, 106131601, 106191601, 106222601, 106272601, 106353601, 106444601, 106464601, 106545601, 106555601, 106717601, 106909601, 106929601, 107000701, 107070701, 107121701, 107232701, 107393701, 107414701, 107424701, 107595701, 107636701, 107646701, 107747701, 107757701, 107828701, 107858701, 107868701, 107888701, 107939701, 107949701, 108070801, 108101801, 108121801, 108151801, 108212801, 108323801, 108373801, 108383801, 108434801, 108464801, 108484801, 108494801, 108505801, 108565801, 108686801, 108707801, 108767801, 108838801, 108919801, 108959801, 109000901, 109101901, 109111901, 109161901, 109333901, 109404901, 109434901, 109444901, 109474901, 109575901, 109656901, 109747901, 109777901, 109797901, 109818901, 109909901, 109929901, 110111011, 110232011, 110252011, 110343011, 110424011, 110505011, 110565011, 110676011, 110747011, 110757011, 110909011, 110949011, 110999011, 111010111, 111020111, 111050111, 111070111, 111181111, 111191111, 111262111, 111272111, 111454111, 111484111, 111515111, 111616111, 111686111, 111757111, 111848111, 112030211, 112060211, 112111211, 112161211, 112171211, 112212211, 112434211, 112494211, 112545211, 112636211, 112878211, 112959211, 112969211, 112989211, 113030311, 113090311, 113111311, 113262311, 113282311, 113474311, 113535311, 113565311, 113616311, 113636311, 113888311, 113939311, 114040411, 114191411, 114232411, 114353411, 114383411, 114484411, 114494411, 114535411, 114727411, 114808411, 114818411, 114848411, 114878411, 114898411, 115000511, 115020511, 115060511, 115111511, 115141511, 115191511, 115212511, 115222511, 115404511, 115464511, 115545511, 115636511, 115737511, 115767511, 115797511, 115828511, 115959511, 116000611, 116010611, 116040611, 116424611, 116505611, 116646611, 116696611, 116757611, 116777611, 116828611, 116868611, 116919611, 117070711, 117101711, 117262711, 117272711, 117323711, 117484711, 117505711, 117515711, 117616711, 117686711, 117757711, 117767711, 117797711, 117818711, 117959711, 118252811, 118272811, 118414811, 118464811, 118525811, 118626811, 118686811, 118696811, 118717811, 118818811, 118848811, 118909811, 118959811, 119010911, 119171911, 119202911, 119343911, 119363911, 119454911, 119585911, 119595911, 119646911, 119676911, 119696911, 119717911, 119787911, 119868911, 119888911, 119969911, 120191021, 120242021, 120434021, 120454021, 120494021, 120535021, 120565021, 120646021, 120808021, 120868021, 120989021, 121080121, 121111121, 121131121, 121161121, 121272121, 121282121, 121393121, 121414121, 121555121, 121747121, 121818121, 121878121, 121939121, 121989121, 122040221, 122232221, 122262221, 122292221, 122333221, 122363221, 122373221, 122393221, 122444221, 122484221, 122535221, 122696221, 122787221, 122858221, 122919221, 123161321, 123292321, 123424321, 123484321, 123494321, 123575321, 123767321, 123838321, 123989321, 124000421, 124080421, 124101421, 124131421, 124252421, 124323421, 124333421, 124434421, 124515421, 124525421, 124626421, 124656421, 124717421, 124737421, 124959421, 124989421, 125000521, 125010521, 125232521, 125252521, 125292521, 125343521, 125474521, 125505521, 125565521, 125606521, 125616521, 125757521, 125838521, 125939521, 125979521, 125999521, 126101621, 126161621, 126181621, 126202621, 126212621, 126323621, 126424621, 126484621, 126535621, 126595621, 126616621, 126676621, 126686621, 126727621, 126737621, 126757621, 126878621, 127060721, 127090721, 127131721, 127212721, 127383721, 127494721, 127545721, 127636721, 127656721, 127686721, 127717721, 127747721, 127828721, 127909721, 127929721, 128070821, 128090821, 128121821, 128181821, 128202821, 128252821, 128262821, 128282821, 128444821, 128474821, 128525821, 128535821, 128595821, 128646821, 128747821, 128787821, 128868821, 128919821, 128939821, 129080921, 129202921, 129292921, 129323921, 129373921, 129484921, 129494921, 129535921, 129737921, 129919921, 129979921, 130020031, 130030031, 130060031, 130141031, 130171031, 130222031, 130333031, 130444031, 130464031, 130545031, 130555031, 130585031, 130606031, 130636031, 130717031, 130767031, 130818031, 130828031, 130858031, 130969031, 131030131, 131111131, 131121131, 131222131, 131252131, 131333131, 131555131, 131565131, 131585131, 131646131, 131676131, 131828131, 132010231, 132191231, 132464231, 132535231, 132595231, 132646231, 132676231, 132757231, 133020331, 133060331, 133111331, 133161331, 133252331, 133474331, 133494331, 133575331, 133686331, 133767331, 133818331, 133909331, 134090431, 134181431, 134232431, 134424431, 134505431, 134525431, 134535431, 134616431, 134757431, 134808431, 134858431, 134888431, 134909431, 134919431, 134979431, 135010531, 135040531, 135101531, 135121531, 135161531, 135262531, 135434531, 135494531, 135515531, 135626531, 135646531, 135707531, 135838531, 135868531, 135878531, 135929531, 135959531, 135979531, 136090631, 136171631, 136222631, 136252631, 136303631, 136363631, 136474631, 136545631, 136737631, 136797631, 136818631, 136909631, 136969631, 137030731, 137040731, 137060731, 137090731, 137151731, 137171731, 137232731, 137282731, 137333731, 137363731, 137424731, 137474731, 137606731, 137636731, 137696731, 137757731, 137808731, 137838731, 137939731, 137999731, 138040831, 138131831, 138242831, 138292831, 138313831, 138383831, 138454831, 138575831, 138616831, 138646831, 138757831, 138898831, 138959831, 138989831, 139131931, 139161931, 139222931, 139252931, 139282931, 139383931, 139474931, 139515931, 139606931, 139626931, 139717931, 139848931, 139959931, 139969931, 139999931, 140000041, 140030041, 140151041, 140303041, 140505041, 140565041, 140606041, 140777041, 140787041, 140828041, 140868041, 140898041, 141020141, 141070141, 141131141, 141151141, 141242141, 141262141, 141313141, 141343141, 141383141, 141484141, 141494141, 141575141, 141595141, 141616141, 141767141, 141787141, 141848141, 142000241, 142030241, 142080241, 142252241, 142272241, 142353241, 142363241, 142464241, 142545241, 142555241, 142686241, 142707241, 142797241, 142858241, 142888241, 143090341, 143181341, 143262341, 143303341, 143454341, 143474341, 143585341, 143636341, 143787341, 143828341, 143919341, 143969341, 144010441, 144020441, 144202441, 144212441, 144313441, 144353441, 144404441, 144434441, 144484441, 144505441, 144707441, 144757441, 144808441, 144818441, 144848441, 144878441, 144898441, 144979441, 144989441, 145020541, 145030541, 145090541, 145353541, 145363541, 145393541, 145464541, 145494541, 145575541, 145666541, 145767541, 146030641, 146040641, 146181641, 146222641, 146252641, 146313641, 146363641, 146505641, 146555641, 146565641, 146676641, 146858641, 146909641, 147191741, 147232741, 147242741, 147313741, 147343741, 147373741, 147434741, 147515741, 147565741, 147616741, 147686741, 147707741, 147757741, 147838741, 147929741, 148020841, 148060841, 148080841, 148414841, 148444841, 148525841, 148545841, 148585841, 148666841, 148686841, 148707841, 148818841, 148858841, 148888841, 148969841, 149000941, 149333941, 149343941, 149484941, 149535941, 149555941, 149616941, 149646941, 149696941, 149858941, 149888941, 149909941, 149919941, 149939941, 150070051, 150151051, 150181051, 150202051, 150272051, 150434051, 150494051, 150505051, 150626051, 150686051, 150727051, 150808051, 150818051, 150979051, 151080151, 151161151, 151212151, 151222151, 151282151, 151353151, 151545151, 151585151, 151656151, 151737151, 151777151, 151858151, 151878151, 151888151, 151959151, 151969151, 151999151, 152090251, 152111251, 152171251, 152181251, 152252251, 152363251, 152393251, 152454251, 152505251, 152565251, 152616251, 152646251, 152666251, 152696251, 152888251, 152939251, 153212351, 153272351, 153292351, 153313351, 153323351, 153404351, 153424351, 153454351, 153484351, 153494351, 153626351, 153808351, 153818351, 153838351, 153979351, 154030451, 154191451, 154252451, 154272451, 154303451, 154323451, 154383451, 154393451, 154474451, 154494451, 154555451, 154575451, 154989451, 155060551, 155141551, 155171551, 155292551, 155313551, 155333551, 155373551, 155424551, 155474551, 155535551, 155646551, 155666551, 155676551, 155808551, 155828551, 155868551, 156151651, 156262651, 156343651, 156424651, 156434651, 156494651, 156545651, 156595651, 156656651, 156707651, 156727651, 156757651, 156848651, 156878651, 156949651, 157090751, 157101751, 157161751, 157252751, 157393751, 157444751, 157555751, 157717751, 157878751, 157888751, 157939751, 157959751, 157989751, 158090851, 158111851, 158222851, 158252851, 158363851, 158474851, 158595851, 158676851, 158696851, 158747851, 158808851, 158858851, 158898851, 158909851, 159020951, 159040951, 159050951, 159121951, 159181951, 159191951, 159202951, 159232951, 159262951, 159292951, 159323951, 159404951, 159464951, 159565951, 159595951, 159646951, 159757951, 159808951, 159919951, 159929951, 159959951, 160020061, 160050061, 160080061, 160101061, 160131061, 160141061, 160161061, 160171061, 160393061, 160545061, 160696061, 160707061, 160717061, 160797061, 160878061, 161171161, 161282161, 161313161, 161363161, 161474161, 161484161, 161535161, 161585161, 161636161, 161787161, 161838161, 161969161, 162040261, 162232261, 162404261, 162464261, 162484261, 162565261, 162686261, 162707261, 162757261, 162898261, 162919261, 162949261, 162959261, 162979261, 162989261, 163101361, 163333361, 163434361, 163464361, 163474361, 163494361, 163515361, 163555361, 163606361, 163686361, 163696361, 163878361, 163959361, 164000461, 164070461, 164151461, 164292461, 164333461, 164454461, 164484461, 164585461, 164616461, 164696461, 164717461, 164727461, 164838461, 165101561, 165161561, 165191561, 165212561, 165343561, 165515561, 165535561, 165808561, 165878561, 165898561, 165919561, 165949561, 166000661, 166080661, 166171661, 166191661, 166404661, 166545661, 166555661, 166636661, 166686661, 166818661, 166828661, 166878661, 166888661, 166929661, 167000761, 167111761, 167262761, 167393761, 167454761, 167474761, 167484761, 167636761, 167646761, 167787761, 167888761, 167898761, 167979761, 168151861, 168191861, 168232861, 168404861, 168505861, 168515861, 168565861, 168818861, 168898861, 168929861, 168949861, 169060961, 169131961, 169141961, 169282961, 169333961, 169383961, 169464961, 169555961, 169606961, 169656961, 169666961, 169686961, 169777961, 169797961, 169858961, 169999961, 170040071, 170060071, 170232071, 170303071, 170333071, 170414071, 170424071, 170484071, 170606071, 170616071, 170646071, 170828071, 170838071, 170909071, 170979071, 171080171, 171262171, 171292171, 171343171, 171565171, 171575171, 171767171, 171919171, 171959171, 172060271, 172090271, 172161271, 172353271, 172363271, 172393271, 172474271, 172585271, 172656271, 172747271, 172767271, 172797271, 172878271, 172909271, 172959271, 173000371, 173030371, 173090371, 173252371, 173373371, 173454371, 173525371, 173585371, 173696371, 173757371, 173777371, 173828371, 173868371, 173888371, 173898371, 173919371, 174080471, 174121471, 174131471, 174181471, 174313471, 174343471, 174595471, 174646471, 174676471, 174919471, 174949471, 174979471, 174989471, 175000571, 175090571, 175101571, 175111571, 175353571, 175444571, 175555571, 175626571, 175747571, 175777571, 175848571, 175909571, 176090671, 176111671, 176141671, 176181671, 176232671, 176313671, 176333671, 176373671, 176393671, 176414671, 176585671, 176636671, 176646671, 176666671, 176696671, 176757671, 176787671, 176888671, 176898671, 176939671, 177121771, 177161771, 177202771, 177242771, 177323771, 177565771, 177616771, 177707771, 177757771, 177868771, 178101871, 178131871, 178141871, 178161871, 178353871, 178414871, 178515871, 178525871, 178656871, 178717871, 178747871, 178878871, 178969871, 178989871, 178999871, 179010971, 179060971, 179222971, 179232971, 179262971, 179414971, 179454971, 179484971, 179717971, 179777971, 179808971, 179858971, 179868971, 179909971, 179969971, 179999971, 180070081, 180101081, 180161081, 180292081, 180515081, 180535081, 180545081, 180565081, 180616081, 180757081, 180959081, 181111181, 181515181, 181545181, 181666181, 181737181, 181797181, 181888181, 182010281, 182202281, 182373281, 182585281, 182616281, 182636281, 182777281, 182858281, 182949281, 183232381, 183626381, 183656381, 183737381, 183898381, 183979381, 183989381, 184030481, 184212481, 184222481, 184303481, 184393481, 184414481, 184545481, 184585481, 184606481, 184636481, 184747481, 184818481, 184878481, 185232581, 185373581, 185393581, 185525581, 185555581, 185595581, 185676581, 185757581, 185838581, 185858581, 185868581, 185999581, 186010681, 186040681, 186050681, 186070681, 186101681, 186131681, 186151681, 186161681, 186424681, 186484681, 186505681, 186565681, 186656681, 186676681, 186787681, 186898681, 187090781, 187101781, 187111781, 187161781, 187272781, 187404781, 187434781, 187444781, 187525781, 187767781, 187909781, 187939781, 187999781, 188010881, 188060881, 188141881, 188151881, 188303881, 188373881, 188414881, 188454881, 188505881, 188525881, 188535881, 188616881, 188636881, 188646881, 188727881, 188777881, 188868881, 188888881, 188898881, 188979881, 189080981, 189131981, 189262981, 189292981, 189464981, 189535981, 189595981, 189727981, 189787981, 189838981, 189898981, 189929981, 190000091, 190020091, 190080091, 190101091, 190252091, 190404091, 190434091, 190464091, 190494091, 190656091, 190696091, 190717091, 190747091, 190777091, 190858091, 190909091, 191090191, 191171191, 191232191, 191292191, 191313191, 191565191, 191595191, 191727191, 191757191, 191838191, 191868191, 191939191, 191969191, 192101291, 192191291, 192202291, 192242291, 192313291, 192404291, 192454291, 192484291, 192767291, 192797291, 192898291, 193000391, 193030391, 193191391, 193212391, 193282391, 193303391, 193383391, 193414391, 193464391, 193555391, 193686391, 193858391, 193888391, 194000491, 194070491, 194121491, 194222491, 194232491, 194292491, 194303491, 194393491, 194505491, 194595491, 194606491, 194787491, 194939491, 194999491, 195010591, 195040591, 195070591, 195151591, 195202591, 195242591, 195353591, 195505591, 195545591, 195707591, 195767591, 195868591, 195878591, 195949591, 195979591, 196000691, 196090691, 196323691, 196333691, 196363691, 196696691, 196797691, 196828691, 196878691, 197030791, 197060791, 197070791, 197090791, 197111791, 197121791, 197202791, 197292791, 197343791, 197454791, 197525791, 197606791, 197616791, 197868791, 197898791, 197919791, 198040891, 198070891, 198080891, 198131891, 198292891, 198343891, 198353891, 198383891, 198454891, 198565891, 198656891, 198707891, 198787891, 198878891, 198919891, 199030991, 199080991, 199141991, 199171991, 199212991, 199242991, 199323991, 199353991, 199363991, 199393991, 199494991, 199515991, 199545991, 199656991, 199767991, 199909991, 199999991]\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        return res[bisect_left(res,n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 我觉得预处理就能够解决问题\n",
    "# 因为回文的原因，所以范围都时很小的\n",
    "def check(x):\n",
    "    if x == 1:\n",
    "        return False\n",
    "    for d in range(2, 1+int(x**0.5)):\n",
    "        if x % d == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "ans = set()\n",
    "for x in range(2*10**4):\n",
    "    if check(x) and str(x) == str(x)[::-1]:\n",
    "        ans.add(x)\n",
    "    if int(str(x) + str(x)[::-1]) < 2 * 10 ** 8:\n",
    "        ans.add(int(str(x) + str(x)[::-1]))\n",
    "    for y in range(10):\n",
    "        if int(str(x) + str(y) +  str(x)[::-1]) < 2 * 10 ** 8:\n",
    "            ans.add(int(str(x) + str(y) +  str(x)[::-1]))\n",
    "ans = sorted([x for x in ans if check(x)])\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        # 1 <= N <= 10^8\n",
    "        return ans[bisect_left(ans, n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 我觉得预处理就能够解决问题\n",
    "# 因为回文的原因，所以范围都时很小的\n",
    "def check(x):\n",
    "    if x == 1:\n",
    "        return False\n",
    "    for d in range(2, 1+int(x**0.5)):\n",
    "        if x % d == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "ans = set()\n",
    "for x in range(10**5):\n",
    "    if check(x) and str(x) == str(x)[::-1]:\n",
    "        ans.add(x)\n",
    "    if int(str(x) + str(x)[::-1]) < 2 * 10 ** 8:\n",
    "        ans.add(int(str(x) + str(x)[::-1]))\n",
    "    for y in range(10):\n",
    "        if int(str(x) + str(y) +  str(x)[::-1]) < 2 * 10 ** 8:\n",
    "            ans.add(int(str(x) + str(y) +  str(x)[::-1]))\n",
    "ans = sorted([x for x in ans if check(x)])\n",
    "\n",
    "class Solution:\n",
    "    def primePalindrome(self, n: int) -> int:\n",
    "        # 1 <= N <= 10^8\n",
    "        return ans[bisect_left(ans, n)]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
